堆排序的構(gòu)造方法探究

杜雙敏

摘要：堆排序作為一種內(nèi)排序算法，其特點(diǎn)是將待排序記錄R[1..n]看成一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中孩子結(jié)點(diǎn)和雙親結(jié)點(diǎn)之間的內(nèi)在關(guān)系，在當(dāng)前無序區(qū)中選擇關(guān)鍵字最?。ɑ蜃畲螅┑挠涗涊敵觯来蔚玫揭粋€(gè)有序序列。堆排序需要解決的兩個(gè)問題：一是如何將一個(gè)無序序列建成一個(gè)堆;二是在輸出堆頂元素之后，把剩余元素調(diào)整成為一個(gè)新堆。堆排序?qū)ι倭康挠涗泚碚f，其優(yōu)點(diǎn)不明顯，但對(duì)大量記錄來說是很有效的。

關(guān)鍵詞：堆排序;完全二叉樹

中圖分類號(hào)：TP399 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）27-0067-03

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

排序就是確定一種排列[Rj1，Rj2，…，Rjn]，設(shè)含n個(gè)記錄的文件{R1，R2，…，Rn】，與其相應(yīng)的關(guān)鍵字為{k1，k2，…，kn），使得與它們相應(yīng)的關(guān)鍵字滿足遞增（或遞減）關(guān)系，即：Kj1≤Kj2≤…，Kjn這種操作過程就稱為排序。簡而言之，排序就是將一個(gè)數(shù)據(jù)元素（或記錄）的任意系列重新排成一個(gè)按關(guān)鍵字有序序列。如果在待排序的表中，存在多個(gè)相同關(guān)鍵字的記錄，經(jīng)過排序后這些相同關(guān)鍵字記錄之間的相對(duì)次序保持不變，則稱這種排序方法是穩(wěn)定的;反之，若相同關(guān)鍵字記錄之間的相對(duì)次序發(fā)生了變化，則稱這種排序方法是不穩(wěn)定的。

1964年J.willioms和Floyd提出了堆排序算法，堆排序是一樹型選擇排序，在其排序過程中的比較次數(shù)達(dá)到樹型選擇水平，同時(shí)又不增加存儲(chǔ)開銷。它的特點(diǎn)是將記錄R[1..n]看成一棵完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)，利用完全二叉樹中孩子結(jié)點(diǎn)和雙親結(jié)點(diǎn)之間的內(nèi)在關(guān)系，在當(dāng)前無序區(qū)中選擇關(guān)鍵字最?。ɑ蜃畲螅┑挠涗涊敵觥Ｔ谳敵龆秧?shù)淖钚≈担ɑ蜃畲笾担┲?，便將剩下的n一1個(gè)元素的序列重新建成一個(gè)堆，則得到n個(gè)元素的次最小值（或次最大值），如此反復(fù)，便得到一個(gè)有序序列，這個(gè)過程我們稱之為堆排序。

堆排序算法的基本思想可以描述為：對(duì)一組待排序記錄的關(guān)鍵字，首先是按堆的定義將它們建成一個(gè)堆，排成一個(gè)序列，從而輸出堆頂?shù)淖钚。ɑ蜃畲螅╆P(guān)鍵字。然后將剩余的n-l個(gè)關(guān)鍵字再重新建成一個(gè)新堆，通常稱為重新調(diào)整成堆，便得到次?。ɑ虼未螅┑年P(guān)鍵字輸出，如此反復(fù)，直到全部關(guān)鍵字排序成有序序列。

堆的定義[1]為：

對(duì)于一個(gè)關(guān)鍵字序列（k1，k2，…，kn】，當(dāng)滿足：

稱此序列為堆（heap），其中，i=1，2，…，[n/2]。滿足條件①稱之為小根堆，滿足條件②稱之為大根堆。

堆排序需要解決的兩個(gè)問題：（1）如何將一個(gè)無序序列建成一個(gè)堆？（2）如何在輸出堆頂元素之后，把剩余的元素調(diào)整成為一個(gè)新的堆？

設(shè)記錄的關(guān)鍵字集合key={49，38，66，90，75，10，20），下面以其為例，來說明堆的構(gòu)造和堆的篩選、重建過程。

1 堆的構(gòu)造

我們可以借助完全二叉樹來描述堆。先把關(guān)鍵字集合key={49，38，66，90，75，10，20】構(gòu)造成一棵完全二叉樹。

依照Floyd篩選法，從完全二叉樹的第i（i=[n/2]）個(gè)結(jié)點(diǎn)序號(hào)開始，對(duì)以此結(jié)點(diǎn)為根的子樹做必要調(diào)整，使該子樹為堆。然后再分別調(diào)整以第i-1，i-2，…，1個(gè)結(jié)點(diǎn)序號(hào)為根的子樹。

1）調(diào)整為小根堆

2）調(diào)整為大根堆

2堆的元素輸出及堆的重建

1）小根堆的元素輸出及堆的重建輸出75，90，完成排序輸出。

2）大根堆的元素輸出及堆的重建

輸出20，10，完成排序輸出。

以上就是堆排序的構(gòu)造過程。堆排序的過程是從一個(gè)無序序列建堆，反復(fù)篩選和進(jìn)行堆調(diào)整的過程。篩選就是自堆頂至葉子的調(diào)整過程。堆調(diào)整就是輸出堆頂元素之后，以堆的最后一個(gè)元素（葉結(jié)點(diǎn)）代替之。

其算法如下：

Void Heapsort（RecType R[]，int n）

{ int i;

RecType temp;

for（i=n/2;i>=l;i--）

Sift（R，i，n）;

for（i=n;i>=2;i--）

{ temp=R[1];

R[1]=R[i]

R[i]=temp;

sift（R，l，i-l）;}

）

Void sift（RecType R[]，int low，int high）

{ int i=low，j=2*i;

RecType temp=R[i];

While （j<=high）

{ if（R[j].key< R[j+l].key&&j

j++;

if（R[j ].key>temp.key）

{R[i]=R[j]

i=J;

j_2*i;）

else break;1

R[i]=temp;）

3 結(jié)束語

堆排序?qū)ι倭康挠涗泚碚f，其優(yōu)點(diǎn)不明顯，但對(duì)大量記錄來說是很有效的。堆排序在最壞的情況下，其平均時(shí)間復(fù)雜度為O（nlog2n），輔助空間O（1），它不穩(wěn)定。

參考文獻(xiàn)：

[1]嚴(yán)蔚敏，吳偉民，數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，1996.

[通聯(lián)編輯：梁書]