合并两个最大堆的算法？

Question

是否有一种有效的算法来合并存储为数组的2个最大堆？

Answer 1

这取决于堆的类型.

如果它是一个标准堆,其中每个节点最多有两个子节点并且填满了叶子最多有两个不同的行,那么合并就不会比O(n)好.

只需将两个数组放在一起,然后用它们创建一个新的堆,它需要O(n).

为了获得更好的合并性能,您可以使用另一个堆变体,如Fibonacci-Heap,它可以合并为O(1)摊销.

更新: 请注意,将第一个堆的所有元素逐个插入第二个堆,反之亦然,因为插入需要O(log(n)).正如您的评论所述,您似乎不知道堆在开始时是如何以最佳方式构建的(对于标准二进制堆也是如此)

我在这里省略了一个证明,但你可以解释这个,因为你已经完成了底层的大部分堆,你不需要交换很多内容来重新建立堆条件.您已经操作了更小的"子堆",这比您将每个元素插入其中一个堆中要好得多=>然后,您将每次在整个堆上操作,每次都需要O(n) .

更新2:二项式堆允许在O(log(n))中合并,并且符合您的O(log(n)^ 2)要求.

Answer 2

大小为n和k的两个二进制堆可以在O(log n*log k)比较中合并.看到