问如何降低使用heap合并多个数组的复杂度？

EN

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

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

1. 创建一个大小为n*k的输出数组(您也可以打印它们)。
2. 创建一个大小为k的最小堆，并将所有数组中的第一个元素插入到堆中
3. 重复以下步骤n*k次。

a)从堆中获取minimum元素(minimum始终位于根)，并将其存储在输出数组中(或打印它)。

b)用从其中提取元素的数组中的下一个元素替换堆根。如果数组没有更多的元素，则将root替换为infinite。在替换了根之后，堆积树。

Time Complexity：主要步骤是3rd步骤，循环运行n*k次。在循环的每一次迭代中，我们调用heapify，这会占用O(Logk)时间。

因此，时间复杂度是O(nk*Logk)。

EDIT1：Heapify确保你总是有最小堆，如果最小的子节点小于父节点，它会将最小的子节点与父节点交换。

这确保了INFINITY元素将保留在堆的底部，而所有k数组中的最小元素将保留在堆的顶部(根)。