algorithm - 合并相同大小的堆

Question

有人可以解释为什么以下合并堆的算法不正确吗？

假设我们有两个(最大)堆 H1 和 H2。

合并它们:

创建一个人工虚拟节点，其键值为负无穷大，并将其放置在根节点上，并附加 H1 和 H2 作为子节点。然后执行 O(log n) 冒泡下降步骤，最终将根交换到叶位置，最终将其删除。生成的结构是合并堆。

我在维基百科和其他地方都看到过合并两个大小相等的堆是一个 Theta(n) 操作的说法，这与我上面写的相矛盾。

Answer 1

至少在通常实现堆时(节点位置中隐含链接)，您似乎几乎忽略的部分(“H1 和 H2 作为子项附加”)本身具有线性复杂性。

作为堆的正常实现，您有一个线性集合(例如，数组)，其中每个元素 N 都有元素 2N 和 2N+1 作为其子元素(例如，对于基于 1 的数组，元素 1 的子元素是元素 2 和 3，元素 2 的子元素是 4 和 5)。因此，在我们到达合并操作的起点之前，您需要交错放置两个堆中的元素。

如果您从显式链接的二叉树开始(仅遵循堆样式规则而不是例如二叉搜索树排序)那么您是对的，合并可以以对数复杂度完成——但我怀疑那篇原始文章打算引用那种结构。