假设我们有 k 个排序数组(每个数组的大小为 n)，在这种情况下使用优先级堆比传统的更好合并(类似于合并排序中使用的那个)，反之亦然？
优先队列方法:在这种方法中，我们有一个最小堆，大小为k(最初，每个堆的第一个元素数组被添加到堆中)。我们现在删除最小元素(从输入数组之一)，将其放入最终数组并从同一输入数组插入一个新元素。这种方法需要 O(kn log k) 时间和 O(kn) 空间。注意:它占用 O(kn) 空间，因为这是最终数组的大小，并且在计算渐近空间复杂度时它决定了堆的大小。
传统合并:在这种方法中，我们合并前 2 个数组以获得大小为 2n 的排序数组。我们对所有输入数组重复此操作，在第一次通过后，我们获得了 k/2 个排序数组，每个数组的大小为 2n。我们重复这个过程，直到我们得到最终的数组。每次通过的时间复杂度为 O(kn)，因为每次比较后都会将一个元素添加到相应的输出数组中。我们有 log k 通行证。因此，总时间复杂度为 O(kn log k)。由于我们可以在每次通过后删除输入数组，因此在任何时候使用的空间都是 O(kn)。
正如我们所见，两种方法的渐近时间和空间复杂度完全相同。那么，我们到底什么时候更喜欢一个呢？我知道对于外部排序，优先级队列方法更好，因为您只需要 O(k) 内存空间，您可以来回读取和写入每个元素到磁盘。但是，当我们有足够的内存时，这些方法如何相互叠加？
最佳答案
操作总数，比较+移动，两种方式都差不多。 k 路合并进行更多比较但移动更少。我的系统有一个 8 路缓存(Intel 3770K 3.5 ghz)，在 4 路合并排序的情况下，允许 4 行缓存用于 4 个输入运行和 1 行缓存用于合并输出运行。在 64 位模式下，有 16 个寄存器可用于工作变量，其中 8 个用于指向每次“运行”(编译器优化)的当前和结束位置的指针。
在我的系统上，我比较了 4 路合并(没有堆，每个元素移动 ~3 次比较)和 2 路合并(每次移动~1 次比较，但传递次数是原来的两倍)，4 路是 1.5 倍比较次数，但移动次数的 0.5 倍，因此操作次数基本相同，但由于缓存问题，第 4 种方式快了大约 15%。
我不知道 16 个寄存器是否足以使 6 路合并更快一点，而 16 个寄存器是否不足以进行 8 路合并(一些工作变量将基于内存/缓存)。尝试使用堆可能无济于事，因为堆将基于内存/缓存(而不是基于寄存器)。
k 向合并主要用于外部排序，由于移动的开销大得多，比较时间被忽略。
关于algorithm - 合并 k 个排序数组 - 优先队列与传统合并排序合并，何时使用哪个？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53356001/