用於從未排序數組生成二進制堆的時間複雜度

Question

任何人都可以解釋爲什麼使用自底向上堆構造從未排序數組生成二進制堆的時間複雜度爲O（n）？

（發現的解決方案迄今：我在托馬斯和古德里奇的書，對內部節點的路徑大小的總和，而構建堆爲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（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）。

N.B.分析取自this。

Answer 2

退房維基百科：

構建堆： 堆可以通過連續插入建成。這種方法需要O（n log n）時間，因爲每個插入需要O（log n）個時間，並且有n個元素。但是，這不是最佳方法。最佳方法首先將元素任意放置在二叉樹上，並考慮shape屬性。然後從最低級開始向上移動，像刪除算法一樣向下移動每個子樹的根，直到堆屬性恢復。

http://en.wikipedia.org/wiki/Binary_heap