堆排序的構造方法探究

杜雙敏

摘要：堆排序作為一種內排序算法，其特點是將待排序記錄R[1..n]看成一棵完全二叉樹的順序存儲結構，利用完全二叉樹中孩子結點和雙親結點之間的內在關系，在當前無序區中選擇關鍵字最小（或最大）的記錄輸出，依次得到一個有序序列。堆排序需要解決的兩個問題：一是如何將一個無序序列建成一個堆;二是在輸出堆頂元素之后，把剩余元素調整成為一個新堆。堆排序對少量的記錄來說，其優點不明顯，但對大量記錄來說是很有效的。

關鍵詞：堆排序;完全二叉樹

中圖分類號：TP399 文獻標識碼：A

文章編號：1009-3044（2020）27-0067-03

開放科學（資源服務）標識碼（OSID）：

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

1964年J.willioms和Floyd提出了堆排序算法，堆排序是一樹型選擇排序，在其排序過程中的比較次數達到樹型選擇水平，同時又不增加存儲開銷。它的特點是將記錄R[1..n]看成一棵完全二叉樹的順序存儲結構，利用完全二叉樹中孩子結點和雙親結點之間的內在關系，在當前無序區中選擇關鍵字最小（或最大）的記錄輸出。在輸出堆頂的最小值（或最大值）之后，便將剩下的n一1個元素的序列重新建成一個堆，則得到n個元素的次最小值（或次最大值），如此反復，便得到一個有序序列，這個過程我們稱之為堆排序。

堆排序算法的基本思想可以描述為：對一組待排序記錄的關鍵字，首先是按堆的定義將它們建成一個堆，排成一個序列，從而輸出堆頂的最小（或最大）關鍵字。然后將剩余的n-l個關鍵字再重新建成一個新堆，通常稱為重新調整成堆，便得到次小（或次大）的關鍵字輸出，如此反復，直到全部關鍵字排序成有序序列。

堆的定義[1]為：

對于一個關鍵字序列（k1，k2，…，kn】，當滿足：

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

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

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

1 堆的構造

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

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

1）調整為小根堆

2）調整為大根堆

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

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

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

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

以上就是堆排序的構造過程。堆排序的過程是從一個無序序列建堆，反復篩選和進行堆調整的過程。篩選就是自堆頂至葉子的調整過程。堆調整就是輸出堆頂元素之后，以堆的最后一個元素（葉結點）代替之。

其算法如下：

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 結束語

堆排序對少量的記錄來說，其優點不明顯，但對大量記錄來說是很有效的。堆排序在最壞的情況下，其平均時間復雜度為O（nlog2n），輔助空間O（1），它不穩定。

參考文獻：

[1]嚴蔚敏，吳偉民，數據結構（C語言版）[M].北京：清華大學出版社，1996.

[通聯編輯：梁書]