合并 2 个最大堆
Merge 2 Max heaps
我需要找到最有效的算法来合并 2 max-heaps。
一些重要事实：堆表示为二叉树，这意味着每个节点都有 3 个字段 - 值（键），指向右的指针 child , 和指向左边的指针 child.
我的想法：取第二个堆的最后一片叶子，将他作为新堆的根。这样我们就得到了一个新的堆，此时左边child是一个合法的最大堆，右边child是一个合法的最大堆。问题（在我看来）只是根不是最大元素这一事实 - 所以我们可以 运行 来自根的函数 Max-Heapify，并且我认为它应该可以解决问题。
最坏情况下的总 运行时间 - O(logn) - 因为将叶子作为根是 O(1)，而 Max-Heapify 是 O(logn).
你怎么看？我对么？
有没有更高效的算法合并2max-heaps？ （请考虑表示是二叉树的事实）
您提出的方法有两个问题。首先是表示：通常堆表示为数组，而不是带有指针的单个节点，这需要 O(n) 交错操作。
即使您对前面的数组存储没问题，也需要考虑 属性 的形状。除非你非常幸运，否则左堆和右堆的大小不会是有效堆的正确大小（也就是说，叶子的深度最多相差 1，并且所有更深的叶子都在上面左边）。
有关合并二进制堆的更多信息，请参阅 Algorithm for merging two max heaps?。但是，如果您不使用数组表示，则并非所有给出的内容都一定适用。
我需要找到最有效的算法来合并 2 max-heaps。
一些重要事实：堆表示为二叉树，这意味着每个节点都有 3 个字段 - 值（键），指向右的指针 child , 和指向左边的指针 child.
我的想法：取第二个堆的最后一片叶子，将他作为新堆的根。这样我们就得到了一个新的堆，此时左边child是一个合法的最大堆，右边child是一个合法的最大堆。问题（在我看来）只是根不是最大元素这一事实 - 所以我们可以 运行 来自根的函数 Max-Heapify，并且我认为它应该可以解决问题。
最坏情况下的总 运行时间 - O(logn) - 因为将叶子作为根是 O(1)，而 Max-Heapify 是 O(logn).
你怎么看？我对么？ 有没有更高效的算法合并2max-heaps？ （请考虑表示是二叉树的事实）
您提出的方法有两个问题。首先是表示：通常堆表示为数组，而不是带有指针的单个节点，这需要 O(n) 交错操作。
即使您对前面的数组存储没问题，也需要考虑 属性 的形状。除非你非常幸运，否则左堆和右堆的大小不会是有效堆的正确大小（也就是说，叶子的深度最多相差 1，并且所有更深的叶子都在上面左边）。
有关合并二进制堆的更多信息，请参阅 Algorithm for merging two max heaps?。但是，如果您不使用数组表示，则并非所有给出的内容都一定适用。