max-heap - 合并 2 个最大堆

Question

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

一些重要的事实：堆表示为二叉树，这意味着每个节点都有 3 个字段 - 值（键）、指向右孩子的指针和指向左孩子的指针。

我的想法：取第二个堆的最后一片叶子，并将他作为新堆的根。所以我们得到一个新的堆，当左孩子是一个合法的最大堆，而右孩子是一个合法的最大堆。问题（在我看来）只是根不是最大元素的事实 - 所以我们可以从根运行函数Max-Heapify，我认为它应该可以解决问题。

最坏情况下的总运行时间 - O(logn) - 因为将叶子作为根是O(1)，而Max-Heapify是O(logn)。

你怎么看待这件事？我对么？是否有更有效的算法来合并 2 个最大堆？（请考虑表示是二叉树的事实）

Answer 1

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

但是，即使您对前面的数组存储感到满意，也需要考虑 shape 属性。除非你非常幸运，否则左堆和右堆的大小不会适合结果成为有效堆（即，叶子的深度最多相差 1，并且所有更深的叶子都在左边）。

有关合并二叉堆的更多信息，请参阅合并两个最大堆的算法？. 但是，如果您不使用数组表示，则并非所有给出的内容都一定适用。