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

Question

谁能解释为什么使用自下而上的堆构造从未排序的数组生成二进制堆的时间复杂度是 O(n) ？

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

谢谢。

score 9 · Accepted Answer

用于从未排序的数组生成二进制堆的正常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(nh)。考虑到 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) 的运行时间。

注：分析取自于此。

score 2 · Accepted Answer

查看维基百科：

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

2 回答 2