排序演算法之堆積排序（Heapsort）解析

no_mkd

一.堆積排序的優缺點（pros and cons）

（還是簡單地說說這個，畢竟沒有必要浪費時間去理解一個糟糕的演算法）

優點：

1. 堆積排序的效率與快排、合併排序相同，都達到了基於比較的排序演算法效率的峰值（時間複雜度為 O(nlogn)）
2. 除了高效之外，最大的亮點就是只需要 O(1) 的輔助空間了，既最高效率又最節省空間，只此一家了
3. 堆積排序效率相對穩定，不像快排在最壞情況下時間複雜度會變成 O(n^2)），所以無論待排序序列是否有序，堆積排序的效率都是 O(nlogn) 不變（注意這裡的穩定特指平均時間複雜度 = 最壞時間複雜度，不是那個「穩定」，因為堆積排序本身是不穩定的）

缺點：（從上面看，堆積排序幾乎是完美的，那麼為什麼最常用的內部排序演算法是快排而不是堆積排序呢？）

1. 最大的也是唯一的缺點就是——堆積的維護問題，實際場景中的數據是頻繁發生變動的，而對於待排序序列的每次更新（增，刪，改），我們都要重新做一遍堆積的維護，以保證其特性，這在大多數情況下都是沒有必要的。（所以快排成為了實際應用中的老大，而堆積排序只能在演算法書裡面頂著光環，當然這麼說有些過分了，當數據更新不很頻繁的時候，當然堆積排序更好些...）

二.內部原理

首先要知道堆積排序的步驟：

1. 構造初始堆積，即根據待排序序列構造第一個大根堆積或小根堆積（大根堆積小根堆積是什麼？這個不解釋了，稻草垛知道吧..）
2. 首尾交換，斷尾重構，即對斷尾後剩餘部分重新構造大（小）根堆積
3. 重複第二步，直到首尾重疊，排序完成

按小根堆積排序結果是降序（或者說是非升序，不要在意這種細節..），按大根堆積排序的結果是升序

上面這句話乍看好像不對（小根堆積中最小元素在堆積頂端，陣列堆積頂端元素就是 a[0]，怎麼會是降序？），不過不用質疑這句話的正確性，看了下面這幾幅圖就明白了：

假設待排序序列是 a[] = {7, 1, 6, 5, 3, 2, 4}，並且按大根堆積方式完成排序

第一步（構造初始堆積）：

{7, 5, 6, 1, 3, 2, 4} 已經滿足了大根堆積，第一步完成

第二步（首尾交換，斷尾重構）：

第三步（重複第二步，直至所有尾巴都斷下來）：

無圖，眼睛畫瞎了，mspaint 實在不好用。。到第二步應該差不多了吧，剩下的用筆也就畫出來了。。

其實核心就是「斷尾」，但可悲的是所有的資料上都沒有明確說出來，可是，還有比「斷尾」更貼切的描述嗎？

三.實作細節

原理介紹中給出的圖基本上也說清楚了實作細節，所以這裡只關注程式碼實作

首先是自己寫出來的大根堆積方式實作：

#include<stdio.h>
//構造大根堆積（讓a[m]到a[n]滿足大根堆積）
void HeapAdjust(int a[], int m, int n){
int temp;
int max;
int lc;//左孩子
int rc;//右孩子
while(1){
	//獲取a[m]的左右孩子
	lc = 2 * m + 1;
	rc = 2 * m + 2;
	//比較a[m]的左右孩子，max記錄較大者的下標
	if(lc &gt;= n){
		break;//不存在左孩子則跳出
	}
	if(rc &gt;= n){
		max = lc;//不存在右孩子則最大孩子為左孩子
	}
	else{
		max = a[lc] &gt; a[rc] ? lc : rc;//左右孩子都存在則找出最大孩子的下標
	}
	//判斷並調整（交換）
	if(a[m] &gt;= a[max]){//父親比左右孩子都大，不需要調整，直接跳出
		break;
	}
	else{//否則把小父親往下換
		temp = a[m];
		a[m] = a[max];
		a[max] = temp;
		//準備下一次迴圈，注意力移動到孩子身上，因為交換之後以孩子為根的子樹可能不滿足大根堆積
		m = max;
	}
}

}
void HeapSort(int a[], int n){
int i,j;
int temp;
//自下而上構造小根堆積（初始堆積）
for(i = n / 2 - 1;i &gt;= 0;i--){//a[n/2 - 1]恰好是最後一個非葉子節點（葉子節點已經滿足小根堆積，只需要調整所有的非葉子節點），一點小小的優化
	HeapAdjust(a, i, n);
}

printf("初始堆積: ");
for(i = 0;i &lt; n;i++){
	printf("%d ", a[i]);
}
printf("\n");

for(i = n - 1;i &gt; 0;i--){
	//首尾交換，斷掉尾巴
	temp = a[i];
	a[i] = a[0];
	a[0] = temp;
	//斷尾後的部分重新調整
	HeapAdjust(a, 0, i);

	/*
	printf("第%d次（i - 1 = %d）: ", n - i, i - 1);
	for(j = 0;j &lt; n;j++){
		printf("%d ", a[j]);
	}
	printf("\n");
	*/
}

}
main(){
//int a[] = {5, 6, 3, 4, 1, 2, 7};
//int a[] = {1, 2, 3, 4, 5, 6, 7};
//int a[] = {7, 6, 5, 4, 3, 2, 1};
int a[] = {7, 1, 6, 5, 3, 2, 4};
int m, n;
int i;
m = 0;
n = sizeof(a) / sizeof(int);
//HeapAdjust(a, m, n);
HeapSort(a, n);
printf("結果: ");
for(i = 0;i &lt; n;i++){
	printf("%d ", a[i]);
}
printf("\n");

}

P.S. 程式碼中註解極其詳盡，因為是完全一步一步自己想著寫出來的，應該不難理解。看程式碼說話，在此多說無益。

接下來給出書本上的大根堆積方式實作：

#include<stdio.h>
void HeapAdjust(int a[], int m, int n){
int i;
int t = a[m];
for(i = 2 * m + 1;i &lt;= n;i = 2 * i + 1){
	if(i &lt; n &amp;&amp; a[i + 1] &gt; a[i])++i;
	if(t &gt;= a[i])break;
	//把空缺位置往下放
	a[m] = a[i];
	m = i;
}
a[m] = t;//只做一次交換，步驟上的優化

}
void HeapSort(int a[], int n){
int i;
int t;
//自下而上構造大根堆積
for(i = n / 2 - 1;i &gt;= 0;--i){
	HeapAdjust(a, i, n - 1);
}

printf("初始堆積: ");
for(i = 0;i &lt; n;i++){
	printf("%d ", a[i]);
}
printf("\n");

for(i = n - 1;i &gt; 0;i--){
	//首尾交換，斷掉尾巴
	t = a[i];
	a[i] = a[0];
	a[0] = t;
	//對斷尾後的部分重新建堆積
	HeapAdjust(a, 0, i - 1);
}

}
main(){
//int a[] = {5, 6, 3, 4, 1, 2, 7};
//int a[] = {1, 2, 3, 4, 5, 6, 7};
//int a[] = {7, 6, 5, 4, 3, 2, 1};
int a[] = {7, 1, 6, 5, 3, 2, 4};
int m, n;
int i;
m = 0;
n = sizeof(a) / sizeof(int);
//HeapAdjust(a, m, n);
HeapSort(a, n);
printf("結果: ");
for(i = 0;i &lt; n;i++){
	printf("%d ", a[i]);
}
printf("\n");

}

P.S. 書本上的程式碼短了不少，不僅僅是篇幅上的優化，也有實實在在的步驟上的優化，細微差別也在註解中說明了。但這種程度的優化卻使得程式碼的可讀性大大降低，所以一次次拿起演算法書，又一次次放下。。(實際應用中我們可以對書本上的程式碼做形式上的優化，在保持其高效性的同時儘可能的提升其可讀性。。)

最後是在研究過書本上的演算法之後，結合其優化措施，寫出的小根堆積方式實作（網上的資料多是大根堆積方式的，其實原理都一樣，這裡只是為了避免枯燥無趣。。）：

#include<stdio.h>
//構造小根堆積（讓a[m]到a[n]滿足小根堆積）
void HeapAdjust(int a[], int m, int n){
int i;
int t = a[m];
int temp;
for(i = 2 * m + 1;i &lt;= n;i = 2 * i + 1){
	//a[m]的左右孩子比較，i記錄較小者的下標
	if(i &lt; n &amp;&amp; a[i + 1] &lt; a[i]){
		i = i + 1;
	}
	if(t &lt;= a[i]){
		break;
	}
	else{//把空缺位置往下換
		//把較小者換上去
		temp = a[m];
		a[m] = a[i];
		a[i] = temp;
		//準備下一次迴圈
		m = i;
	}
}

}
void HeapSort(int a[], int n){
int i, j;
int temp;
//自下而上構造小根堆積（初始堆積）
for(i = n / 2 - 1;i &gt;= 0;i--){//a[n/2 - 1]恰好是最後一個非葉子節點（葉子節點已經滿足小根堆積，只需要調整所有的非葉子節點），一點小小的優化
	HeapAdjust(a, i, n);
}

printf("初始堆積: ");
for(i = 0;i &lt; n;i++){
	printf("%d ", a[i]);
}
printf("\n");

//把每個元素都調整到應該去的位置
for(i = n - 1; i &gt; 0;i--){
	//首尾交換
	temp = a[i];
	a[i] = a[0];
	a[0] = temp;
	//斷尾後剩餘部分重新調整
	HeapAdjust(a, 0, i - 1);
}

}
main(){
//int a[] = {7, 6, 5, 4, 3, 2, 1};
//int a[] = {1, 5, 6, 4, 3, 2, 7};
int a[] = {1, 2, 3, 4, 5, 6, 7};
int m, n;
int i;
m = 0;
n = sizeof(a) / sizeof(int);
//HeapAdjust(a, m, n);
HeapSort(a, n);
printf("結果: ");
for(i = 0;i &lt; n;i++){
	printf("%d ", a[i]);
}
printf("\n");

}

P.S. 註解依然詳盡，看程式碼，不廢話

四.總結

堆積排序的步驟就幾個字而已：建堆積 -> 首尾交換，斷尾重構 -> 重複第二步，直到斷掉所有尾巴

還有比這更清晰更明了的描述嗎？

到現在我們已經掌握了幾個有用的排序演算法了：

快速排序、合併排序、堆積排序

那麼實際應用中要如何選擇呢？有這些選擇標準：

1. 若 n 較小，採用插入排序和簡單選擇排序。由於直接插入排序所需的記錄移動操作比簡單選擇排序多，所以當記錄本身資訊量比較大時，用簡單選擇排序更好。
2. 若待排序序列基本有序，可以採用直接插入排序或者冒泡排序
3. 若 n 較大，應該採用時間複雜度最低的演算法，比如快排，堆積排序或合併排序
4. • 細分的話，當數據隨機分佈時，快排最佳（這與快排的硬體優化有關，在之前的博文中有提到過）
   • 堆積排序只需要一個輔助空間，而且不會出現快排的最壞情況
   • 快排和堆積排序都是不穩定的，如果要求穩定的話可以採用合併排序，還可以把直接插入排序和合併排序結合起來，先用直接插入獲得有序碎片，再合併，這樣得到的結果也是穩定的，因為直接插入是穩定的

說明：在理解「斷尾」的過程中參考了前輩的博文，特此感謝