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