合并两个最大堆的算法？
有没有一种有效的算法来合并存储为数组的2个max-heap？
回答：
这取决于堆的类型。
如果这是一个标准堆，其中每个节点最多有两个子节点，并且叶子被放在最多两个不同的行中而被填满，那么合并的效果就不会比O（n）好。
只需将两个数组放在一起，并从中创建一个新堆，就需要O（n）。
为了获得更好的合并性能，可以使用另一个可以在O（1）摊销后合并的Fibonacci-Heap之类的堆变量。
请注意，将第一个堆的所有元素一个接一个地插入第二个堆，或者反之亦然，因为插入需要O（log（n））。正如您的评论所指出的，您似乎并不知道在一开始如何最佳地构建堆（再次针对标准二进制堆）
- 创建一个数组，并以任意顺序放入两个堆的元素
- 现在从最低级别开始。最低级别包含大小为1的琐碎最大堆，因此已完成此级别
- 提升水平。当违反了“子堆”之一的堆条件时，将“子堆”的根与更大的子项交换。之后，完成2级
- 移至级别3。违反堆条件时，请像以前一样处理。将其与较大的子项交换下来，然后递归处理，直到所有内容匹配到第3级为止
- …
- 当到达顶部时，您在O（n）中创建了一个新堆。
我在这里省略了一个证明，但是您可以解释这一点，因为您已经在底层完成了大部分堆操作，而不必交换很多内容来重新建立堆条件。您已经对较小的“子堆”进行了操作，这要比将每个元素插入其中一个堆中的操作要好得多=>然后，您将对整个堆进行每次操作，每次都需要O（n）
。
二项式堆允许合并O（log（n））并符合O（log（n）^ 2）的要求。
以上是 合并两个最大堆的算法？ 的全部内容， 来源链接： utcz.com/qa/431857.html
