堆的定義:???
?????????n個(gè)關(guān)鍵字序列K
l，K
2，…，K
n稱(chēng)為堆，當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)(簡(jiǎn)稱(chēng)為堆性質(zhì))：
??? (1) k
i≤K
2i且k
i≤K
2i+1 或(2)K
i≥K
2i且k
i≥K
2i+1(1≤i≤
)
??? 若將此序列所存儲(chǔ)的向量R[1..n]看做是一棵完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹(shù)：樹(shù)中任一非葉結(jié)點(diǎn)的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點(diǎn)的關(guān)鍵字。
?????????堆的這個(gè)性質(zhì)使得可以迅速定位在一個(gè)序列之中的最小(大)的元素.
?????????堆排序算法的過(guò)程如下:1)得到當(dāng)前序列的最小(大)的元素 2)把這個(gè)元素和最后一個(gè)元素進(jìn)行交換,這樣當(dāng)前的最小(大)的元素就放在了序列的最后,而原先的最后一個(gè)元素放到了序列的最前面 3)的交換可能會(huì)破壞堆序列的性質(zhì)(
注意此時(shí)的序列是除去已經(jīng)放在最后面的元素),因此需要對(duì)序列進(jìn)行調(diào)整,使之滿足于上面堆的性質(zhì).重復(fù)上面的過(guò)程,直到序列調(diào)整完畢為止.
//?array是待調(diào)整的堆數(shù)組,i是待調(diào)整的數(shù)組元素的位置,length是數(shù)組的長(zhǎng)度
void?HeapAdjust(int?array[],?int?i,?int?nLength)
{
????int?nChild,?nTemp;
????for?(nTemp?=?array[i];?2?*?i?+?1?<?nLength;?i?=?nChild)
????{
????????//?子結(jié)點(diǎn)的位置是?父結(jié)點(diǎn)位置?*?2?+?1
????????nChild?=?2?*?i?+?1;
????????//?得到子結(jié)點(diǎn)中較大的結(jié)點(diǎn)
????????if?(nChild?!=?nLength?-?1?&&?array[nChild?+?1]?>?array[nChild])
????????????++nChild;
????????//?如果較大的子結(jié)點(diǎn)大于父結(jié)點(diǎn)那么把較大的子結(jié)點(diǎn)往上移動(dòng),替換它的父結(jié)點(diǎn)
????????if?(nTemp?<?array[nChild])
????????{
????????????array[i]?=?array[nChild];
????????}
????????else????//?否則退出循環(huán)
????????{
????????????break;
????????}
????}
????//?最后把需要調(diào)整的元素值放到合適的位置
????array[i]?=?nTemp;
}
//?堆排序算法
void?HeapSort(int?array[],?int?length)
{
????//?調(diào)整序列的前半部分元素,調(diào)整完之后第一個(gè)元素是序列的最大的元素
????for?(int?i?=?length?/?2?-?1;?i?>=?0;?--i)
????{
????????HeapAdjust(array,?i,?length);
????}
????//?從最后一個(gè)元素開(kāi)始對(duì)序列進(jìn)行調(diào)整,不斷的縮小調(diào)整的范圍直到第一個(gè)元素
????for?(int?i?=?length?-?1;?i?>?0;?--i)
????{
????????//?把第一個(gè)元素和當(dāng)前的最后一個(gè)元素交換,
????????//?保證當(dāng)前的最后一個(gè)位置的元素都是在現(xiàn)在的這個(gè)序列之中最大的
????????Swap(&array[0],?&array[i]);
????????//?不斷縮小調(diào)整heap的范圍,每一次調(diào)整完畢保證第一個(gè)元素是當(dāng)前序列的最大值
????????HeapAdjust(array,?0,?i);
????}
}一個(gè)測(cè)試及輸出的結(jié)果,在每次HeapAdjust之后顯示出來(lái)當(dāng)前數(shù)組的情況
before?Heap?sort:
71?18?151?138?160?63?174?169?79?78?
//?開(kāi)始調(diào)整前半段數(shù)組元素
71?18?151?138?160?63?174?169?79?78?
71?18?151?169?160?63?174?138?79?78?
71?18?174?169?160?63?151?138?79?78?
71?169?174?138?160?63?151?18?79?78?
174?169?151?138?160?63?71?18?79?78?
//?開(kāi)始進(jìn)行全局的調(diào)整
169?160?151?138?78?63?71?18?79?174?
160?138?151?79?78?63?71?18?169?174?
151?138?71?79?78?63?18?160?169?174?
138?79?71?18?78?63?151?160?169?174?
79?78?71?18?63?138?151?160?169?174?
78?63?71?18?79?138?151?160?169?174?
71?63?18?78?79?138?151?160?169?174?
63?18?71?78?79?138?151?160?169?174?
18?63?71?78?79?138?151?160?169?174? 動(dòng)畫(huà)演示:
http://202.113.89.254/DataStructure/DS/web/flashhtml/duipaixu.htm