algorithm - 合并两个最大堆的算法？

Question

是否有一种有效的算法来合并存储为数组的 2 个最大堆？

Answer 1

这取决于堆的类型。

如果它是一个标准堆，其中每个节点最多有两个子节点，并且叶子在最多两个不同的行上被填满，那么对于合并，你不可能比 O(n) 更好。

只需将两个数组放在一起并从中创建一个新的堆，这需要 O(n)。

为了获得更好的合并性能，您可以使用另一个堆变体，例如可以在 O(1) 摊销中合并的 Fibonacci-Heap。

更新： 请注意，将第一个堆的所有元素一个接一个地插入第二个堆会更糟糕，反之亦然，因为插入需要 O(log(n))。正如您的评论所述，您似乎一开始并不知道堆是如何以最佳方式构建的（同样适用于标准二叉堆）

1. 创建一个数组并以任意顺序放入两个堆的元素
2. 现在从最低级别开始。最低级别包含大小为 1 的琐碎最大堆，因此此级别已完成
3. 向上移动一个级别。当“子堆”之一的堆条件被违反时，将“子堆”的根交换为其更大的孩子。之后，2级完成
4. 移至第 3 级。当违反堆条件时，像以前一样处理。将其与更大的孩子交换并递归处理，直到所有内容都匹配到第 3 级
5. ...
6. 当您到达顶部时，您在 O(n) 中创建了一个新堆。

我在这里省略了一个证明，但您可以解释这一点，因为您已经在底层完成了大部分堆，您不必交换太多内容来重新建立堆条件。您已经在小得多的“子堆”上进行了操作，这比将每个元素插入其中一个堆时要好得多 => 然后，您每次都将在整个堆上进行操作，每次都需要 O(n) .

更新 2：二项式堆允许合并 O(log(n)) 并符合您的 O(log(n)^2) 要求。

Answer 2

两个大小为 n 和 k 的二进制堆可以在 O(log n * log k) 比较中合并。看

约尔格-R。Sack 和 Thomas Strothotte，一种用于合并堆的算法，Acta Informatica 22 (1985), 172-186。

Answer 3

我认为在这种情况下您要寻找的是二项式堆。

二项式堆是二项式树的集合，是可合并堆家族的成员。2+ 二项式堆上的联合（合并）最坏情况下的运行时间是 O(lg n)。

有关更多信息，请参阅http://en.wikipedia.org/wiki/Binomial_heap 。