0 
Example: List 1: [1, 4, 5, 8, 9]
     List 2: [3, 4, 4, 6]
     List 3: [0, 2, 8]
    Would yield the following result:

    Iterator -> [0, 1, 2, 3, 4, 4, 4, 5, 6, 8, 8, 9]

本着空间复杂性的精神，我不愿意创建一个接受 k 个列表并将 List 的内容合并到另一个 List 的“合并”方法。这是可以使用“最小堆”实现的 k 路合并问题吗？任何指针都会非常有帮助。

public class CustomListIterator<E> implements Iterator<E>{

private boolean canAddIterators = true;
private boolean balanceTreeIteratorFlag = false;
private E f_element;
private E s_element;
private Iterator<E> left;
private Iterator<E> right;
private final Comparator<E> comparator;

public CustomListIterator(Comparator<E> comparator){
    this.comparator = comparator;
}

public CustomListIterator(Iterator<E> left, Iterator<E> right, Comparator<E> comparator){
    this.left = left;
    this.right = right;
    this.comparator = comparator;
}

public void addIterator(Iterator<E> iterator){
    if (!canAddIterators)
        throw new ConcurrentModificationException();

    if (right == null){
        right = iterator;
        return;
    }else if (left == null){
        left = iterator;
        return;
    }

    if (!balanceTreeIteratorFlag){
        right = balanceTreeOfIterators(iterator, right);
    }else{
        left = balanceTreeOfIterators(iterator, left);
    }

    balanceTreeIteratorFlag = !balanceTreeIteratorFlag;
}

private Iterator<E> balanceTreeOfIterators(Iterator<E> iterator_1, Iterator<E> iterator_2){
    if (iterator_2 instanceof CustomListIterator){
        ((CustomListIterator<E>)iterator_2).addIterator(iterator_1);
    } else{
        iterator_2 = new CustomListIterator<E>(iterator_1, iterator_2, comparator);
    }
    return iterator_2;
}

public boolean hasNext() {
    if (canAddIterators){
        if (left != null && left.hasNext()){
            f_element = left.next();
        }
        if (right != null && right.hasNext()){
            s_element = right.next();
        }
    }
    canAddIterators = false;
    return f_element != null || s_element != null;
}

public E next() {
    E next;
    if (canAddIterators){
        if (left.hasNext()){
            f_element = left.next();
        }
        if (right.hasNext()){
            s_element = right.next();
        }
    }

    canAddIterators = false;

    if (s_element == null && f_element == null){
        throw new NoSuchElementException();
    }

    if (f_element == null){
        next = s_element;
        s_element = right.hasNext() ? right.next() : null;
        return next;
    }

    if (s_element == null){
        next = f_element;
        f_element = left.hasNext() ? left.next() : null;
        return next;
    }

    return findNext();
}

public void remove() {

}

private E findNext(){
    E next;
    if (comparator.compare(f_element, s_element) < 0){
        next = f_element;
        f_element = left.hasNext() ? left.next() : null;
        return next;
    }
    next = s_element;
    s_element = right.hasNext() ? right.next() : null;
    return next;
}

}

我不认为这是最好的方法（使用树）。关于如何仅通过覆盖 next() hasNext() 和 remove() 来实现这一点的任何建议？

4

1 回答 1

4

合并多个排序列表基本上有三种不同的方法：

  1. 连续的双向合并
  2. 分而治之
  3. 基于优先队列

在下面的讨论中，n是指所有列表中组合的项目总数。k指列表的数量。

案例 1 是最容易设想的，但也是效率最低的。假设您有四个列表，A、B、C 和 D。使用此方法，您可以合并 A 和 B 以创建 AB。然后合并 AB 和 C 以创建 ABC。最后，将 ABC 与 D 合并以创建 ABCD。该算法的复杂度接近 O(n*k)。您迭代 A 和 B 三次，C 两次，D 一次。

分而治之的解决方案是合并 A 和 B 以创建 AB。然后合并 C 和 D 以创建 CD。然后合并 AB 和 CD 以创建 ABCD。在最好的情况下，当列表具有相似数量的项目时，这种方法是 O(n * log(k))。但是如果列表的长度变化很大，这个算法的运行时间可能会接近 O(n*k)。

有关这两种算法的更多信息，请参阅我的博客文章，仔细看看成对合并。有关分而治之方法的更多详细信息，请参阅合并多个列表的不同方法。

基于优先级队列的合并工作如下：

Create a priority queue to hold the iterator for each list
while the priority queue is not empty
    Remove the iterator that references the smallest current number
    Output the referenced value
    If not at end of iterator
        Add the iterator back to the queue

该算法在最坏的情况下被证明是 O(n * log(k)) 。您可以看到每个列表中的每个项目都被添加到优先级队列中一次，并从优先级队列中删除一次。但是队列k在任何时候都只包含项目。所以内存需求很小。

Java 中迭代器的实现使优先级队列的实现稍显不便，但可以通过一些辅助类轻松解决。最重要的是，我们需要一个迭代器，它可以让我们在不消费的情况下查看下一个项目。我称之为 a PeekableIterator，它看起来像这样：

// PeekableIterator is an iterator that lets us peek at the next item
// without consuming it.
public class PeekableIterator<E> implements Iterator<E> {
    private final Iterator<E> iterator;
    private E current;
    private boolean hasCurrent;

    public PeekableIterator(Iterator<E> iterator) {
        this.iterator = iterator;
        if (iterator.hasNext()) {
            current = iterator.next();
            hasCurrent = true;
        }
        else {
            hasCurrent = false;
        }
    }

    public E getCurrent() {
        // TODO: Check for current item
        return current;
    }

    public boolean hasNext() {
        return hasCurrent;
    }

    public E next() {
        // TODO: Error check to see if there is a current
        E rslt = current;
        if (iterator.hasNext()) {
            current = iterator.next();
        }
        else {
            hasCurrent = false;
        }
        return rslt;
    }

    public void remove() {
        iterator.remove();
    }

PeekableIterator然后，由于优先级队列将保存迭代器而不是单个项，因此我们需要一个比较器来比较两个接口的当前项。这很容易创建：

// IteratorComparator lets us compare the next items for two PeekableIterator instances.
public class IteratorComparator<E> implements Comparator<PeekableIterator<E>> {
    private final Comparator<E> comparator;

    public IteratorComparator(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    public int compare(PeekableIterator<E> t1, PeekableIterator<E> t2) {
        int rslt = comparator.compare(t1.getCurrent(), t2.getCurrent());
        return rslt;
    }
}

这两个类是您编写的代码的更正式的实现，用于获取和比较各个迭代器的下一项。

最后，MergeIterator初始化 aPriorityQueue<PeekableIterator>以便您可以调用hasNext和next方法来迭代合并的列表：

// MergeIterator merges items from multiple sorted iterators
// to produce a single sorted sequence.
public class MergeIterator<E> implements Iterator<E> {
    private final IteratorComparator<E> comparator;
    private final PriorityQueue<PeekableIterator<E>> pqueue;

    // call with an array or list of sequences to merge
    public MergeIterator(List<Iterator<E>> iterators, Comparator<E> comparator) {
        this.comparator = new IteratorComparator<E>(comparator);

        // initial capacity set to 11 because that's the default,
        // and there's no constructor that lets me supply a comparator without the capacity.
        pqueue = new PriorityQueue<PeekableIterator<E>>(11, this.comparator);

        // add iterators to the priority queue
        for (Iterator<E> iterator : iterators) {
            // but only if the iterator actually has items
            if (iterator.hasNext())
            {
                pqueue.offer(new PeekableIterator(iterator));
            }
        }
    }

    public boolean hasNext() {
        return pqueue.size() > 0;
    }

    public E next() {
        PeekableIterator<E> iterator = pqueue.poll();
        E rslt = iterator.next();
        if (iterator.hasNext()) {
            pqueue.offer(iterator);
        }
        return rslt;
    }

    public void remove() {
        // TODO: Throw UnsupportedOperationException
    }
}

我创建了一个小测试程序来演示它是如何工作的：

private void DoIt() {
    String[] a1 = new String[] {"apple", "cherry", "grape", "peach", "strawberry"};
    String[] a2 = new String[] {"banana", "fig", "orange"};
    String[] a3 = new String[] {"cherry", "kumquat", "pear", "pineapple"};

    // create an ArrayList of iterators that we can pass to the
    // MergeIterator constructor.
    ArrayList<Iterator<String>> iterators = new ArrayList<Iterator<String>> (
            Arrays.asList(
                    Arrays.asList(a1).iterator(),
                    Arrays.asList(a2).iterator(),
                    Arrays.asList(a3).iterator())
    );

    // String.CASE_INSENSITIVE_ORDER is a Java 8 way to get
    // a String comparator. If there's a better way to do this,
    // I don't know what it is.
    MergeIterator<String> merger = new MergeIterator(iterators, String.CASE_INSENSITIVE_ORDER);
    while (merger.hasNext())
    {
        String s = merger.next();
        System.out.println(s);
    }
}

我对分治法和优先级队列合并的性能比较表明，分治法可以比使用优先级队列更快，具体取决于比较的成本。当比较便宜时（例如原始类型），成对合并会更快，即使它做的工作更多。随着键比较变得更加昂贵（如比较字符串），优先级队列合并具有优势，因为它执行的比较更少。

更重要的是，成对合并需要两倍于优先队列方法的内存。我的实现使用了 FIFO 队列，但即使我构建了一个树，成对合并也需要更多内存。此外，正如您的代码所示，如​​果您想实现成对合并，您仍然需要PeekableIteratorand类（或类似的东西）。IteratorComparator

有关这两种方法的相对性能的更多详细信息，请参阅测试合并性能。

由于我上面详述的原因，我得出结论，优先级队列合并是最好的方法。

于 2017-10-31T14:47:39.640 回答