??對(duì)于幾個(gè)元素的關(guān)鍵字序列{K₁，K₂，…，K_n}，當(dāng)且僅當(dāng)滿足下列關(guān)系時(shí)稱其為堆，其中 2i 和2i+1應(yīng)不大于n。
{ K i ≤ K 2 i + 1 K i ≤ K 2 i 或 { K i ≥ K 2 i + 1 K i ≥ K 2 i {\huge \{}^{K_i≤K_{2i}} _{K_i≤K_{2i+1}} \quad\quad 或 \quad\quad {\huge \{}^{K_i≥K_{2i}} _{K_i≥K_{2i+1}} {Ki?≤K2i+1?Ki?≤K2i??或{Ki?≥K2i+1?Ki?≥K2i??
??若將此序列對(duì)應(yīng)的一維數(shù)組(即以一維數(shù)組作為序列的存儲(chǔ)結(jié)構(gòu))看成是一個(gè)完全二叉樹，則堆的含義表明，完全二叉樹中所有非終端結(jié)點(diǎn)的值均不小于(或不大子) 其左、右孩子,結(jié)點(diǎn)的值。因此，在一個(gè)堆中，堆頂元素(即完全二義樹的根結(jié)點(diǎn))必為序列中的最大元素(或最小元素)，并且堆中的任一棵子樹也都是堆。若堆頂為最小元素，則稱為小根堆；若堆頂為最大元素，則稱為大根堆。
??推排序的基本思想是：對(duì)一組待排序記錄的關(guān)鍵字，首先按堆的定義排成一個(gè)序列(即建立初始堆)，從而可以輸出堆項(xiàng)的最大關(guān)鍵字(對(duì)于大根堆而言)，然后將剩余的關(guān)鍵字再調(diào)整成新堆，便得到次大的關(guān)鍵字，如此反復(fù)，直到全部關(guān)鍵字排成有序序列為止。
??初始堆的建立方法是：將待排序的關(guān)鍵字分放到一棵完全二叉樹的各個(gè)結(jié)點(diǎn)中(此時(shí)完全二叉樹并不一定具備堆的特性)，顯然，所有 i> $[\frac{n}{2}]$的結(jié)點(diǎn) K_i 都沒有子結(jié)點(diǎn)，以這樣的 K_i 為根的子樹已經(jīng)是堆，因此初始建堆可從完全二叉樹的第 i {i=$[\frac{n}{2}]$} 個(gè)結(jié)點(diǎn) K_i 開始，通過(guò)調(diào)整，逐步使以K[$\frac{n}{2}$]、K[$\frac{n}{2}$]-1、K[$\frac{n}{2}$]-2、…、K₂、K₁為根的子樹滿足堆的定義。
??在對(duì)K_i 為根的子樹建堆的過(guò)程中，可能需要交換 K_i 與K_2i 或(K_2i+1)的值，如此一來(lái)，以K_2i(或K_2i+i)為根的子樹可能不再滿足堆的定義，則應(yīng)繼續(xù)以 K_2i(或K_2i+1)為根進(jìn)行調(diào)整。如此層層地遞推下去，可能會(huì)一直延伸到葉子結(jié)點(diǎn)時(shí)為止。這種方法就像過(guò)篩子一樣，把最大(或最小)的關(guān)鍵字一層一層地篩選出來(lái)，最后輸出堆頂?shù)淖畲?或最小) 元素。
??【函數(shù)】將一個(gè)整型數(shù)組中的元素調(diào)整成大根堆。

void HeapAdjust(int data[], int s, int m)
/*在 data[s..m]所構(gòu)成的一個(gè)元素序列中，除了 data[s]外，其余元素均滿足大頂堆的定義*/
/*調(diào)整元素 data[s]的位置，使 data[s..m]成為一個(gè)大頂堆*/
{int tmp,j;tmp = data[s];							/*備份元素 data[s]，為其找到適當(dāng)位置后再插入*/for(j= 2*s+1; j<=m; j=j*2+1){			/*沿值較大的孩子結(jié)點(diǎn)向下篩選*/if(j<m && data[j]<data[j+1]) ++j;	/*j是值較大的元素的下標(biāo)*/if(tmp>=data[i]) break;data[s] = data[jl; s =j;			/*用s記錄待插入元素的位置 (下標(biāo)) */}/*for*/data[s]=tmp;							/*將備份元素插入由 s 所指出的插入位置*/
}/*HeapAdjust*/

??調(diào)整成新堆：假設(shè)輸出堆頂元素之后，以堆中最后一個(gè)元素替代，那么根結(jié)點(diǎn)的左、右子樹均為堆，此時(shí)只需自上至下進(jìn)行調(diào)整即可。
??【函數(shù)】用堆排序方法對(duì)整型數(shù)組進(jìn)行非遞減排序。

void HeapSort(int data[], int n)		/*數(shù)組 data[0..n-1]中的n個(gè)元素進(jìn)行堆排序*/
{inti;int tmp;for(i = n/2-1; i>=0; --i)			/*將 data[0..n-1]調(diào)整為大根堆*/HeapAdjust(data, i, n-1);for(i= n-l; i>0; --i){tmp=data[0]; data[0]=data[i];data[i] = tmp;					/*堆頂元素 data[0]與序列末的元素 data[i]交換*/HeapAdjust(data,0,i-1);			/*待排元素的個(gè)數(shù)減 1，將 data[0..i-1]重新調(diào)整為大根堆*/}/*for*/
}/*HeapSort*/

??為序列(55,60,40,10,80,65,15,5,75)建立初始大根堆的過(guò)程如下圖所示

??調(diào)整為新堆過(guò)程如下圖所示

??對(duì)于記錄數(shù)較少的文件來(lái)說(shuō)，堆排序的優(yōu)越性并不明顯，但對(duì)子大量的記錄來(lái)說(shuō)，堆排序是很有效的。堆排序的整個(gè)算法時(shí)間是山建立初始堆和不斷調(diào)整堆這兩部分時(shí)同構(gòu)成的?？梢宰C明，堆排序算法的時(shí)間復(fù)雜度為 O(n ㏒ n)。此外，堆排序只需要一個(gè)記錄大小的輔助空間。堆排序是一種不穩(wěn)定的排序方法。