任何一个可以解释为什么使用自下而上堆建设从无序阵列生成二元堆的时间复杂度为O（n）？

Can any one explain why the time complexity for generating a binary heap from a unsorted array using bottom-up heap construction is O(n) ?

（解决方案迄今发现：我发现在托马斯和古德里奇的书，对内部节点的路径大小的总和，而构建堆为2n-1，但还是不明白自己的解释）

(Solution found so far: I found in Thomas and Goodrich book that the total sum of sizes of paths for internal nodes while constructing the heap is 2n-1, but still don't understand their explanation)

感谢。

推荐答案

普通的 BUILD堆的步骤从无序阵列生成二进制堆实现如下：

Normal BUILD-HEAP Procedure for generating a binary heap from an unsorted array is implemented as below :

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堆的过程需要为O（n LG电子n）的时间。

Here HEAPIFY Procedure takes O(h) time, where h is the height of the tree, and there are O(n) such calls making the running time O(n h). Considering h=lg n, we can say that BUILD-HEAP Procedure takes O(n lg n) time.

有关更严格的分析，我们可以观察到，大多数节点的高度是小的。 实际上，在任何高度h，可存在至多CEIL（N /（2 ^ H 1））节点，我们可以很容易地通过感应证明。 因此，运行时间的 BUILD堆的可写为，

For tighter analysis, we can observe that heights of most nodes are small. Actually, at any height h, there can be at most CEIL(n/ (2^h +1)) nodes, which we can easily prove by induction. So, the running time of BUILD-HEAP can be written as,

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     

因此​​，运行时间变

Hence, running time becomes,

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

所以，这给邻运行时间（n）。

So, this gives a running time of O(n).

N.B。该分析是从这个。

N.B. The analysis is taken from this.