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)。因此，在我们到达合并操作的起点之前，您需要交错两个堆中的元素。

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

Answer 2

如果您将其实现为树，则您的解决方案是正确的。但正如 Jerry 所提到的，合并基于数组的堆不能在亚线性时间内完成。

根据合并的频率和大小，我建议您使用虚拟堆。您可以将其实现为堆堆（带有数组）。几次合并后，您可以将多个内部堆懒惰地合并为一个大堆。