从未排序数组生成二进制堆的时间复杂度

Question

任何人都可以解释为什么使用自下而上堆构造从未排序数组生成二进制堆的时间复杂度为O（n）？

（到目前为止找到的解决方案：我在Thomas和Goodrich的书中发现，构建堆时内部节点的路径大小总和是2n-1，但仍然不理解他们的解释）

谢谢。

Answer 1

正常的BUILD-HEAP从未排序的数组生成二进制堆的过程实现如下：

BUILD-HEAP(A)
 heap-size[A] ← length[A]
  for i ← length[A]/2 downto 1
   do HEAPIFY(A, i)

这里HEAPIFY过程需要O（h）时间，其中h是树的高度，并且有O（n）个这样的调用使得运行时间为O（n h）。考虑到h = lg n，我们可以说BUILD-HEAP过程需要O（n lg n）时间。

为了进行更严格的分析，我们可以观察到大多数节点的高度很小。实际上，在任何高度h，最多可以有CEIL（n /（2 ^ h +1））节点，我们可以通过归纳轻松证明这些节点。因此，BUILD-HEAP的运行时间可写为，

lg n                     lg n
∑ n/(2^h+1)*O(h)  = O(n* ∑ O(h/2^h)) 
h=0                      h=0

现在，

∞   
∑ k*x^k = X/(1-x)^2
k=0              
               ∞ 
Putting x=1/2, ∑h/2^h = (1/2) / (1-1/2)^2 = 2
               h=0

因此，运行时间变成，

lg n                     ∞   
O(n* ∑ O(h/2^h))  = O(n* ∑ O(h/2^h))  = O(n)
h=0                      h=0

因此，这给出了O（n）的运行时间。

注：分析来自this。

Answer 2

查看维基百科：

构建堆：可以通过连续插入来构建堆。这种方法需要O（n log n）时间，因为每次插入需要O（log n）时间并且有n个元素。然而，这不是最佳方法。最佳方法首先将元素任意放在二叉树上，尊重shape属性。然后从最低级别开始向上移动，按照删除算法向下移动每个子树的根，直到堆属性恢复。