合并两个最大堆的算法? [英] Algorithm for merging two max heaps?
问题描述
是否有一种有效的算法来合并存储为数组的 2 个最大堆?
Is there an efficient algorithm for merging 2 max-heaps that are stored as arrays?
推荐答案
这取决于堆的类型.
如果它是一个标准堆，其中每个节点最多有两个子节点，并且叶节点最多位于两个不同的行上，那么对于合并，您将无法获得比 O(n) 更好的方法.
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.
只需将两个数组放在一起并从中创建一个新的堆，该堆需要 O(n).
Just put the two arrays together and create a new heap out of them which takes O(n).
为了获得更好的合并性能，您可以使用另一种堆变体，例如 Fibonacci-Heap，它可以在 O(1) 中摊销合并.
For better merging performance, you could use another heap variant like a Fibonacci-Heap which can merge in O(1) amortized.
更新:请注意，将第一个堆的所有元素一个接一个地插入到第二个堆中会更糟，反之亦然，因为插入需要 O(log(n)).正如您的评论所述，您似乎不知道堆是如何在开始时以最佳方式构建的(对于标准二元堆)
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)
- 创建一个数组并以任意顺序放入两个堆的元素
- 现在从最低级别开始.最低级别包含大小为 1 的平凡最大堆，因此该级别已完成
- 提升一个级别.当子堆"之一的堆条件被违反时，将子堆"的根与其较大的孩子交换.之后，完成第 2 级
- 移动到第 3 级.当堆条件被违反时，像以前一样处理.将其与更大的孩子交换并递归处理，直到一切都匹配到第 3 级
- ...
- 当您到达顶部时，您在 O(n) 中创建了一个新堆.
我在这里省略了一个证明，但你可以解释这一点，因为你已经在底层完成了大部分的堆，你不必交换很多内容来重新建立堆条件.您已经在更小的子堆"上进行了操作，这比将每个元素插入其中一个堆时所做的要好得多 => 然后，您每次都将在整个堆上进行操作，每次都需要 O(n).
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.
更新 2: 二项式堆允许在 O(log(n)) 中合并，并且符合您的 O(log(n)^2) 要求.
Update 2: A binomial heap allows merging in O(log(n)) and would conform to your O(log(n)^2) requirement.
这篇关于合并两个最大堆的算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
