合并k个排序数组-比较两种解决方案

Question

如果我有K个包含每个N个元素的已排序数组，例如：

[0, 1, 2]
[1, 6, 8]
[10, 11, 12]

我知道可以使用堆来合并它们，通过循环所有列表及其元素并将它们插入堆中，然后每次以O(KN * log(KN))的时间复杂度获取最小值。

我在网上查过，另一个常见的解决方案似乎是使用只有K个元素的最小堆，并将所有K个列表的第一个项目插入到堆中，然后取出最小的数并将指针移动到拥有该最小项的列表。

除了第二种方法具有更高效的内存需求（第二种情况下为O(K)），第二种方法是否在时间上更有效？

可选奖励分：是否存在比以上两种更好的算法？

- Dean

Answer 1

第二个版本的运行时间应该为O(KN* log(K))，因为你需要对每个元素执行一次堆化（log (K)），共有(N*K)个元素。所以，是的，它更快。我想不到更有效的解决方法。

- SaiBot

Answer 2

第一种方法适用于您具有足够内存对所有输入列表进行排序的情况，但是更简单的方法是执行已排序列表之间的k路合并，并使用额外空间（K个元素的列表）来跟踪每个输入列表所在位置的索引。这是一个O(K^2 * N)的解决方案。

哪种方法更好——第一种方法还是k路合并，取决于K相对于N的大小，不要忘记第一种方法构建堆的成本为O(KN)。为了给您一个想法：

k=5; n=100
k*n*log(k*n)
=> 3107
k*k*n
=> 2500

k=100; n=100
k*n*log(k*n)
=> 92103
k*k*n
=> 1000000

第二种方法使用的内存更少，这非常重要！当输入列表不适合内存时，我们会从每个列表中取一个元素，将其放入堆中，确定下一个进入最终结果的元素，并将其写入输出，相应地更新堆：这是复杂度为 O(KN * log(K))。再次说明一下，以便理解：

k=5; n=100
k*n*log(k)
=> 804

k=100; n=100
k*n*log(k)
=> 46051

底线：当输入数据适合内存且k较小的时候，使用k路归并而不是第一种方法；正如@btilly所指出的那样，第二种方法从理论上讲是最好的，但实际考虑可能会使k路归并更快。像往常一样：最好的策略是用一些真实的数据进行分析，并选择获胜者！

- Óscar López

---

嘿，感谢你的回答！K路归并不会更慢吗？因为你每一步都必须进行K次比较（与部分排序的堆树相比，堆树只需要进行少量比较）。 - Dean

请您能否解释一下O(KN)解决方案？ 也许我没有理解您的意思，但是选择下一个元素将需要O(K)时间，因此它将成为O(K^2*N)解决方案。 - alper

@alper 你说得对，我没有考虑到选择下一个元素的成本:/ 我会更新我的答案。不过无论如何，如果我们使用堆，我们也必须支付构建它的O(KN)成本。最终，最佳方案取决于K的大小。 - Óscar López

@alper 第一种方法的时间复杂度为O(log(KN))。 - Óscar López

第二种方法在理论上严格优于第一种方法和k路归并。当比较便宜且CPU中的管道停顿是一个问题时，k路归并可能在实践中更好，因为您可以使用比较和交换操作，从而分支预测变得完美。 - btilly

Answer 3

第一个答案是O(KN * log(KN))。 第二个是O(KN * log(K))，因此更好。总的来说，很难做得比这个更好。

话虽如此，有时在实践中可以改进它。不要把最小元素放入堆中，而是像归并排序一样创建合并树。然后添加逻辑，当您似乎从合并的一侧拉取时，请尝试跳转并查找运行。

如果K很大，比较昂贵，并且您的数据有很多运行，则胜利可能非常显着。

请参见https://en.wikipedia.org/wiki/Timsort以了解此类排序算法的示例，并已经对许多真实用例进行了精细调整。

- btilly