data-structures - 合并具有线性复杂度的堆数组

Question

如何将两个堆数组合并为一个平衡堆数组并仍然保持线性复杂度？我读到的关于合并堆的大部分材料都需要 O(nlogn)。

Answer 1

我们有两个大小为 N 的堆。每个堆都可以表示为一个数组，参见 parent 和 child 之间的关系。所以我们有两个堆排序的数组。我们需要通过将一个数组的所有元素添加到另一个数组的末尾来将这两个数组连接成一个数组。

所以现在我们有一个大小为 2N 的数组，但它不是堆排序的。为了使数组堆有序，它需要线性数量的比较，因此需要线性时间。（请参阅自下而上的堆构建 -在 O(n) 中构建堆的顺序）

Answer 2

有一个 O(n) 时间算法（有时称为“heapify”），给定 n 个总值，从这些值创建一个最大堆。这个较早的答案描述了算法并解释了它的运行时间。您可以使用此算法来合并两个最大堆，方法是创建一个新数组来存储这些最大堆中的所有值，并应用 heapify 算法从它们中构造一个新堆。

但是，如果您知道您将经常合并堆，那么有比二叉堆更好的数据结构。例如，二项式堆、配对堆和倾斜堆都支持在 O(log n) 时间内进行融合。

希望这可以帮助！