雖然我在閱讀「算法導論」，但我想知道爲什麼HEAPSORT需要時間O（nlgn），而BUILD-MAX-HEAP需要時間O（n）。爲什麼BUILD-MAX-HEAP花費O（nlgn）時間O（n）而HEAP-SORT花費O（nlgn）時間？
HEAPSORT從A.length downto 2開始循環，調用MAX-HEAPIFY。
BUILD-MAX-HEAP在A.length/2 downto 1的底部開始循環，調用MAX-HEAPIFY。
MAX-HEAPIFY需要時間O（lgn）。我想知道是什麼導致BUILD-MAX-HEAP比HEAPSORT更快。
在構建堆時，我們始終從底部開始「HEAPIFY」元素，但在對它進行排序時，我們始終將「HEAPIFY」放在最上面的元素。在這兩種情況下，高度不同，但一點要注意：
* 在構建堆，我們在底部heapify謊言，最大的元素，他們得到非常少的高度，因此heapify爲O（n），但在排序時，我們總是讓最頂層的元素堆積。儘管高度正在下降，但並不像先前的情況那樣有利。 *
我希望你明白我在說什麼。
在heapsort算法中，您總是擔心「堆狀況」，它指出沒有元素應該放置在堆中高於較大元素的位置，並且如果存在違反堆狀況的元素，那麼您修復它。修復堆狀況需要多少努力取決於元件底部高於需要固定的程度。
在構建堆的初始階段，元素的後半部分不會違反堆條件，因爲下面沒有任何內容。四分之一的元素違反了堆的條件，但只是堆的底部一行，所以只需要一步來修復堆狀況。然後八分之一的元素違反了堆的條件，但是堆的底部只有兩行，所以只需要兩個步驟。
如果合計需要的步數，則可以得到n/4 * 1 + n/8 * 2 + n/16 * 3 + n/32 * 4 ...，小於n。但是當你通過反覆地將第一個具有最大數字的元素排列在數組末尾時，堆的條件是總是違反了堆的頂部，（log n）行在底部之上，所以log n步需要修復堆狀況。
請參閱[Wikipedia]（https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap）瞭解爲什麼heapifying是O（n）的證明。 –
heapsort基本上以MAX-HEAPIFY開頭（儘管它可能會稍微有點不同），然而，heapsort然後繼續*從堆中移除每個元素*。正是這個額外的步驟使它成爲O（n log n）而不僅僅是O（n）。 – harold