構建堆時從數組中間調用heapify的原因

Question

構建堆時，我們從樹的中間位置（即floor（n/2））開始調用max_heapify(A,i)，直到以減少的方式維護根堆屬性。我已經閱讀了一些背後的原因，但我仍然不明白爲什麼。請問有人可以解釋這個原因嗎？

謝謝。

Answer 1

如果我們這樣做，在最壞的情況下，時間複雜度是線性的（證明的觀點是要觀察當一個元素被篩選下來時，另一個元素上移並且元素一旦擁有就不會下降因此，每片葉子下降的次數爲零，葉片上一級的每個元素的上升次數最多爲1次，如果我們明確地計算出這個總和，結果是O(N))。

如果我們從端部開始並過篩元件向上的時間複雜度是O(N log N)（例如，如果陣列被反轉）。

綜上所述，這種方式更有效。

注意：我們可以從最後一個元素開始，但是葉子永遠不會下降，所以它是沒有用的（雖然時間複雜度會保持線性）。