合并2最大堆

Question

我需要找到最有效的算法合并2个最大堆。

一些重要的事实:堆被表示为一个二叉树，这意味着每个节点都有三个字段--值(键)、指向右子节点的指针和指向左子节点的指针。

我的想法是:取第二堆的最后一页，把他作为新堆的根。所以我们得到一个新的堆，当左子是一个合法的最大堆，而右边的子堆是一个合法的最大堆。问题(在我看来)只是根不是最大元素的事实，所以我们可以从根运行函数Max-Heapify，我认为它应该解决这个问题。

在最坏的情况下- O(logn) --因为使叶子作为根是O(1)，而Max-Heapify是O(logn)。

你觉得那个怎么样？我说的对吗？是否有更有效的算法来合并2个最大堆？(请考虑到表示是二叉树这一事实)

Answer 1

您提出的方法有两个问题。首先是表示:通常堆被表示为数组，而不是单独的具有指针的节点，这需要O(n)交织操作。

不过，即使您对前面的数组存储没有意见，也需要考虑shape属性。除非您非常幸运，否则左堆和右堆的大小将不足以使结果成为一个有效的堆(也就是说，在这个堆中，叶子的深度最多相差1，而所有较深的叶子都在左边)。

有关合并二进制堆的更多信息，请参见Algorithm for merging two max heaps?。但是，如果您没有使用数组表示，那么并不是所有给定的内容都一定适用。