合并两个最大堆的算法？

Question

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

Answer 1

这取决于堆的类型。

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

只需将两个数组放在一起，然后用它们创建一个新的堆，这需要 O(n)。

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

更新:请注意，将第一个堆的所有元素一个一个地插入到第二个堆或反之亦然，因为插入需要 O(log(n))。正如您的评论所述，您似乎并不知道堆在开始时是如何优化构建的(同样对于标准二进制堆)

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

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

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