arrays - 如何降低使用堆合并多个数组的复杂度？

Question

我对这个问题中提出的想法进行了编码：合并排序数组，如下所示：Big-O complex calculation for a merge and sort function。

可以看出，这种方法的复杂性超出了预期。有没有更好的方法（除了使用 LINQ）？如果有的话，这种方法的根本缺陷是什么？

Answer 1

我们可以使用 Min Heap 在 O(nk*Logk) 时间内合并数组。

n= 数组的最大大小，k= 数组的数量。

1. 创建一个大小的输出数组n*k（您也可以打印它们）。
2. 创建一个最小大小的堆k并将所有数组中的第一个元素插入堆中
3. 重复以下步骤n*k几次。
   a）从堆中获取最小元素（最小值始终在根）并将其存储在输出数组中（或打印它）。
   b) 将堆根替换为从中提取元素的数组中的下一个元素。如果数组没有更多元素，则将 root 替换为无限。替换根后，堆化树。

时间复杂度：主要步骤是3rd步骤，循环运行n*k次数。在循环的每次迭代中，我们调用 heapify ，这需要O(Logk)时间。
因此，时间复杂度为O(nk*Logk)。

EDIT1：Heapify 确保您始终拥有min-heap，如果该最小值小于 parent ，它会将最小的子节点与父节点交换。

这确保INFINITY元素将保持在底部，并且所有k数组中的最小元素保持在 heap 的顶部（根）。