是否有一种有效的算法来合并存储为数组的 2 个最大堆？
问问题
36352 次
3 回答
21
这取决于堆的类型。
如果它是一个标准堆，其中每个节点最多有两个子节点，并且叶子在最多两个不同的行上被填满，那么对于合并，你不可能比 O(n) 更好。
只需将两个数组放在一起并从中创建一个新的堆，这需要 O(n)。
为了获得更好的合并性能，您可以使用另一个堆变体，例如可以在 O(1) 摊销中合并的 Fibonacci-Heap。
更新： 请注意，将第一个堆的所有元素一个接一个地插入第二个堆会更糟糕，反之亦然，因为插入需要 O(log(n))。正如您的评论所述，您似乎一开始并不知道堆是如何以最佳方式构建的（同样适用于标准二叉堆）
- 创建一个数组并以任意顺序放入两个堆的元素
- 现在从最低级别开始。最低级别包含大小为 1 的琐碎最大堆，因此此级别已完成
- 向上移动一个级别。当“子堆”之一的堆条件被违反时，将“子堆”的根交换为其更大的孩子。之后，2级完成
- 移至第 3 级。当违反堆条件时，像以前一样处理。将其与更大的孩子交换并递归处理，直到所有内容都匹配到第 3 级
- ...
- 当您到达顶部时，您在 O(n) 中创建了一个新堆。
我在这里省略了一个证明，但您可以解释这一点，因为您已经在底层完成了大部分堆，您不必交换太多内容来重新建立堆条件。您已经在小得多的“子堆”上进行了操作，这比将每个元素插入其中一个堆时要好得多 => 然后，您每次都将在整个堆上进行操作，每次都需要 O(n) .
更新 2：二项式堆允许合并 O(log(n)) 并符合您的 O(log(n)^2) 要求。
于 2009-10-20T16:02:19.330 回答
9
两个大小为 n 和 k 的二进制堆可以在 O(log n * log k) 比较中合并。看
约尔格-R。Sack 和 Thomas Strothotte，一种用于合并堆的算法，Acta Informatica 22 (1985), 172-186。
于 2009-11-02T02:43:22.333 回答
1
我认为在这种情况下您要寻找的是二项式堆。
二项式堆是二项式树的集合，是可合并堆家族的成员。2+ 二项式堆上的联合（合并）最坏情况下的运行时间是 O(lg n)。
有关更多信息，请参阅http://en.wikipedia.org/wiki/Binomial_heap 。
于 2014-03-31T19:23:15.817 回答