輸入：n個(gè)數(shù)的一個(gè)序列 (A[1..n])

輸出：輸入序列的一個(gè)排序，滿(mǎn)足b1≤b2≤…≤bn。

堆

表示堆的數(shù)組A包括兩個(gè)屬性：A.length給出數(shù)組元素的個(gè)數(shù)，A.heap-size表示有多少個(gè)堆元素存儲(chǔ)在該數(shù)組中。也就是說(shuō)，雖然A[1..A.length]可能都存有數(shù)據(jù)，但只有A[1..A.heap-size]中存放的是堆的有效元素。這里, 0 ≤ A.heap-size ≤ A.length。

（二叉）堆數(shù)組A是一個(gè)近似的完全二叉樹(shù)，樹(shù)的根結(jié)點(diǎn)是A[1]，這樣，給定一個(gè)結(jié)點(diǎn)的下標(biāo)i，它的父節(jié)點(diǎn)、左孩子和右孩子的下標(biāo)：

`PARENT(i): return i/2// i>>1

LEFT(i): return2i// i<<1

RIGHT(i): return2i+1// i<<1 + 1

`

最大堆：堆的最大元素存放在根結(jié)點(diǎn)中。并且，在任一子樹(shù)中，該子樹(shù)所包含的所有結(jié)點(diǎn)的值都不大于該子樹(shù)根結(jié)點(diǎn)的值。即：A[PARENT(i) ≥ A[i]。堆排序使用最大堆。

最小堆：堆的最小元素存放在根結(jié)點(diǎn)中。并且，在任一子樹(shù)中，該子樹(shù)所包含的所有結(jié)點(diǎn)的值都不小于該子樹(shù)根結(jié)點(diǎn)的值。即：A[PARENT(i) ≤ A[i]。最小堆常用來(lái)構(gòu)造優(yōu)先隊(duì)列。

堆中結(jié)點(diǎn)的高度：該結(jié)點(diǎn)到葉結(jié)點(diǎn)最長(zhǎng)簡(jiǎn)單路徑上邊的數(shù)目。

堆的高度：根結(jié)點(diǎn)的高度。O(lgn)。其中，n為堆中元素個(gè)數(shù)。