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

Question

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

Answer 1

有一个O(N)堆算法(有时称为“-time”)，它在给定n个值的情况下，从这些值创建一个最大堆。This earlier answer describes the algorithm and explains its runtime.您可以使用此算法合并两个最大堆，方法是创建一个新数组来存储来自这些最大堆的所有值，并应用heapify算法来构造一个新的堆。

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

希望这能有所帮助！

Answer 2

我们得到了两个大小为N的堆。每个堆都可以表示为一个数组See relation between parent and child。所以我们有两个数组，它们是堆排序的。我们需要通过将一个数组的所有元素添加到另一个数组的末尾来将这两个数组连接成一个数组。

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