合并两个最大堆的算法？
是否有一种有效的算法来合并存储为数组的 2 个最大堆？
Is there an efficient algorithm for merging 2 max-heaps that are stored as arrays?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
是否有一种有效的算法来合并存储为数组的 2 个最大堆？
Is there an efficient algorithm for merging 2 max-heaps that are stored as arrays?
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（3）
这取决于堆的类型。
如果它是一个标准堆，其中每个节点最多有两个子节点，并且叶子节点最多位于两个不同的行上，那么您无法获得比 O(n) 更好的合并效果。
只需将两个数组放在一起并创建一个新的堆，这需要 O(n) 的时间。
为了获得更好的合并性能，您可以使用另一种堆变体，例如斐波那契堆，它可以按 O(1) 分摊合并。
更新：
请注意，将第一个堆的所有元素逐个插入到第二个堆或反之亦然会更糟糕，因为插入需要 O(log(n))。
正如您的评论所述，您似乎不知道堆在开始时是如何最佳构建的（同样是标准二进制堆）
我在这里省略了一个证明，但您可以对此进行解释，因为您已经在底层完成了大部分堆操作，无需交换太多内容来重新建立堆条件。您已经在更小的“子堆”上进行了操作，这比您将每个元素插入其中一个堆时要好得多=>那么，你每次都会在整个堆上进行操作，每次都需要 O(n) 。
更新 2： 二项式堆允许在 O(log(n)) 中进行合并，并且符合您的 O(log(n)^2) 要求。
It depends on what the type of the heap is.
If it's a standard heap where every node has up to two children and which gets filled up that the leaves are on a maximum of two different rows, you cannot get better than O(n) for merge.
Just put the two arrays together and create a new heap out of them which takes O(n).
For better merging performance, you could use another heap variant like a Fibonacci-Heap which can merge in O(1) amortized.
Update:
Note that it is worse to insert all elements of the first heap one by one to the second heap or vice versa since an insertion takes O(log(n)).
As your comment states, you don't seem to know how the heap is optimally built in the beginning (again for a standard binary heap)
I omit a proof here but you can explain this since you have done most of the heap on the bottom levels where you didn't have to swap much content to re-establish the heap condition. You have operated on much smaller "sub heaps" which is much better than what you would do if you would insert every element into one of the heaps => then, you willoperate every time on the whole heap which takes O(n) every time.
Update 2: A binomial heap allows merging in O(log(n)) and would conform to your O(log(n)^2) requirement.
大小为 n 和 k 的两个二进制堆可以在 O(log n * log k) 比较中合并。请参阅
Jörg-R。 Sack 和 Thomas Strothotte，合并堆的算法，Acta Informatica 22 (1985), 172-186。
Two binary heaps of sizes n and k can be merged in O(log n * log k) comparisons. See
Jörg-R. Sack and Thomas Strothotte, An algorithm for merging heaps, Acta Informatica 22 (1985), 172-186.
我认为在这种情况下您要寻找的是二项式堆。
二项式堆是二项式树的集合，是可合并堆家族的成员。在堆中总共有 n 个项目的 2 个以上二项式堆上进行联合（合并）的最坏情况运行时间是 O(lg n)。
有关详细信息，请参阅 http://en.wikipedia.org/wiki/Binomial_heap。
I think what you're looking for in this case is a Binomial Heap.
A binomial heap is a collection of binomial trees, a member of the merge-able heap family. The worst-case running time for a union (merge) on 2+ binomial heaps with n total items in the heaps is O(lg n).
See http://en.wikipedia.org/wiki/Binomial_heap for more information.