给定每个列表中最多N个元素的K个排序列表，在所有项目上返回已排序的迭代器

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。 这是一个可以使用“min Heap”实现的k-way合并问题。 任何指针都会非常有用。

 public class CustomListIterator implements Iterator{ private boolean canAddIterators = true; private boolean balanceTreeIteratorFlag = false; private E f_element; private E s_element; private Iterator left; private Iterator right; private final Comparator comparator; public CustomListIterator(Comparator comparator){ this.comparator = comparator; } public CustomListIterator(Iterator left, Iterator right, Comparator comparator){ this.left = left; this.right = right; this.comparator = comparator; } public void addIterator(Iterator 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 balanceTreeOfIterators(Iterator iterator_1, Iterator iterator_2){ if (iterator_2 instanceof CustomListIterator){ ((CustomListIterator)iterator_2).addIterator(iterator_1); } else{ iterator_2 = new CustomListIterator(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（）来实现这一点的任何建议？

Answer 1

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

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 

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

Java中迭代器的实现使得优先级队列实现稍微不方便，但可以通过一些辅助类轻松修复。 最重要的是，我们需要一个迭代器，让我们可以在不消耗它的情况下查看下一个项目。 我将其称为PeekableIterator ，如下所示：

 // PeekableIterator is an iterator that lets us peek at the next item // without consuming it. public class PeekableIterator implements Iterator { private final Iterator iterator; private E current; private boolean hasCurrent; public PeekableIterator(Iterator 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 implements Comparator> { private final Comparator comparator; public IteratorComparator(Comparator comparator) { this.comparator = comparator; } public int compare(PeekableIterator t1, PeekableIterator t2) { int rslt = comparator.compare(t1.getCurrent(), t2.getCurrent()); return rslt; } } 

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

最后， MergeIterator初始化一个PriorityQueue以便您可以调用hasNext和next方法来迭代合并列表：

 // MergeIterator merges items from multiple sorted iterators // to produce a single sorted sequence. public class MergeIterator implements Iterator { private final IteratorComparator comparator; private final PriorityQueue> pqueue; // call with an array or list of sequences to merge public MergeIterator(List> iterators, Comparator comparator) { this.comparator = new IteratorComparator(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>(11, this.comparator); // add iterators to the priority queue for (Iterator 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 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> iterators = new ArrayList> ( 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 merger = new MergeIterator(iterators, String.CASE_INSENSITIVE_ORDER); while (merger.hasNext()) { String s = merger.next(); System.out.println(s); } } 

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

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

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

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