堆積排序(Heap Sort)演算法，利用完全二元樹來排序的演算法
文章推薦指數： 80 %
堆積排序(Heap Sort)演算法是利用完全二元樹(Complete Binary Tree)，也就是堆積(Heap)結構來完成排序的演算法。
雖然說要用到堆積結構，看起來好像很 ...
MagicLen
內容
堆積排序(HeapSort)演算法，利用完全二元樹來排序的演算法
2019年4月5日
MagicLen
研究分享、Go、Java、NodeJS、Rust、演算法
編輯
本篇文章更新於
2022年6月7日20時
堆積排序(HeapSort)演算法是利用完全二元樹(CompleteBinaryTree)，也就是堆積(Heap)結構來完成排序的演算法。
雖然說要用到堆積結構，看起來好像很複雜似的，但其實這個只要一般的陣列結構(可以直接用要排序的陣列來製作)就能實作出來，而且實作出來的速度保證不會太慢，再怎麼差都會有O(nlogn)的時間複雜度。
堆積排序法(HeapSort)
堆積排序法的概念
堆積排序有法兩個大步驟，第一個是把要排序的陣列製作成「最小堆積」(MinHeap)或是「最大堆積」(MaxHeap)。
如果要將陣列遞增排序的話就使用最大堆積；如果要遞減排序的話就使用最小堆積。
接下來的步驟就是利用最大堆積和最小堆積來進行排序，方法和建立最大堆積或是最小堆積時是幾乎一樣的。
什麼是完全二元樹？完全二元樹是一種二元樹，它只允許最後一層(最底下那層)的節點數量可以不必填滿(若頂層是第1層，則第n層的最大節點數量為2n-1)。
例如以下結構即為完全二元樹：
5
/\
13
/\/
624
什麼是最小堆積？最小堆積就是上層節點數值必定會小於下層節點數值的完全二元樹。
例如以下結構即為最小堆積：
1
/\
25
/\/
463
什麼是最大堆積？最大堆積就是上層節點數值必定會大於下層節點數值的完全二元樹。
例如以下結構即為最大堆積：
6
/\
53
/\/
421
陣列可以依照索引順序，由左至右、由上到下表示出一個完全二元樹。
例如以上的最大堆積，可以是以下這個陣列：
索引012345
數值653421
堆積排序法的過程
假設現在有個陣列資料，內容如下：
索引0123456789
數值698130389247613279
要如何將它遞增排列呢？
我們先將這個陣列用完全二元樹的結構來表示，如下：
69
/\
/\
/\
8130
/\/\
/\/\
389247
/\/
613279
由於我們要進行遞增，因此要先將這個完全二元樹變成最大堆積。
於是我們從最下面的兩層開始，把比上層大的元素交換到上層。
首先看到47，由於它沒有子節點，因此還不用交換。
69
/\
/\
/\
8130
/\/\
/\/\
389247*
/\/
613279
2，也沒有子節點，因此不用交換。
69
/\
/\
/\
8130
/\/\
/\/\
3892*47
/\/
613279
再來看到9，9有一個值為79的子節點。
由於79比9大，所以要交換上來。
69
/\
/\
/\
8130
/\/\
/\/\
389*247
/\/
613279↑
69
/\
/\
/\
8130
/\/\
/\/\
3879+247
/\/
61329*
此時9已沒有子節點了，結束交換。
再來看到38，38有兩個子節點，最大的子節點為61。
由於61比38大，所以要交換上來。
69
/\
/\
/\
8130
/\/\
/\/\
38*79247
/\/
61↑329
69
/\
/\
/\
8130
/\/\
/\/\
61+79247
/\/
38*329
此時38已沒有子節點了，結束交換。
依此類推，剩下的最大堆積的建構過程如下：
69
/\
/\
/\
8130*
/\/\
/\/\
6179247↑
/\/
38329
69
/\
/\
/\
8147+
/\/\
/\/\
6179230*
/\/
38329
69
/\
/\
/\
81*47
/\/\
/\/\
6179230
/\/
38329
69*
/\
/\
/\
81↑47
/\/\
/\/\
6179230
/\/
38329
81+
/\
/\
/\
69*47
/\/\
/\/\
6179↑230
/\/
38329
81+
/\
/\
/\
7947
/\/\
/\/\
6169*230
/\/
38329
81
/\
/\
/\
7947
/\/\
/\/\
6169230
/\/
38329
至此，最大堆積就建立好了！
接下來的工作就是排序啦！由於我們現在已經知道這個結構中的最大值是最頂層的節點，且我們要把陣列做遞增排列。
所以我們可以直接把頂層的節點，也就是最大值與陣列的最後一個元素做交換，如此一來我們的遞增排序就已經排好一個元素了。
9*
/\
/\
/\
79↑47
/\/\
/\/\
6169230
/\/
383281-
但別忘了要繼續維持住我們的最大堆積條件，所以還是得做交換才行。
由於此時81已經在陣列的正確位置上，我們可以直接把它從最大堆積的考慮範圍中排除，不要再去動它了。
79+
/\
/\
/\
9*47
/\/\
/\/\
6169↑230
/\/
383281-
79+
/\
/\
/\
6947
/\/\
/\/\
619*230
/\/
383281-
79
/\
/\
/\
6947
/\/\
/\/\
619230
/\/
383281-
接下來就是讓32要與這個最大堆積結構中的最大值，也就是最頂層的節點做交換啦！之後的步驟都跟剛才把81換下來時一樣，如下：
32*
/\
/\
/\
69↑47
/\/\
/\/\
619230
/\/
3879-81-
69+
/\
/\
/\
32*47
/\/\
/\/\
61↑9230
/\/
3879-81-
69+
/\
/\
/\
6147
/\/\
/\/\
32*9230
/\/
38↑79-81-
69+
/\
/\
/\
6147
/\/\
/\/\
389230
/\/
32*79-81-
69
/\
/\
/\
6147
/\/\
/\/\
389230
/\/
3279-81-
32*
/\
/\
/\
61↑47
/\/\
/\/\
389230
/\/
69-79-81-
61+
/\
/\
/\
32*47
/\/\
/\/\
38↑9230
/\/
69-79-81-
61+
/\
/\
/\
3847
/\/\
/\/\
32*9230
/\/
69-79-81-
61
/\
/\
/\
3847
/\/\
/\/\
329230
/\/
69-79-81-
30*
/\
/\
/\
3847↑
/\/\
/\/\
329261-
/\/
69-79-81-
47+
/\
/\
/\
3830*
/\/\
/\/\
329261-
/\/
69-79-81-
47
/\
/\
/\
3830
/\/\
/\/\
329261-
/\/
69-79-81-
2*
/\
/\
/\
38↑30
/\/\
/\/\
32947-61-
/\/
69-79-81-
38+
/\
/\
/\
2*30
/\/\
/\/\
32↑947-61-
/\/
69-79-81-
38+
/\
/\
/\
3230
/\/\
/\/\
2*947-61-
/\/
69-79-81-
38
/\
/\
/\
3230
/\/\
/\/\
2947-61-
/\/
69-79-81-
9*
/\
/\
/\
32↑30
/\/\
/\/\
238-47-61-
/\/
69-79-81-
32+
/\
/\
/\
9*30
/\/\
/\/\
238-47-61-
/\/
69-79-81-
32
/\
/\
/\
930
/\/\
/\/\
238-47-61-
/\/
69-79-81-
2*
/\
/\
/\
930↑
/\/\
/\/\
32-38-47-61-
/\/
69-79-81-
30+
/\
/\
/\
92*
/\/\
/\/\
32-38-47-61-
/\/
69-79-81-
30
/\
/\
/\
92
/\/\
/\/\
32-38-47-61-
/\/
69-79-81-
2*
/\
/\
/\
9↑30-
/\/\
/\/\
32-38-47-61-
/\/
69-79-81-
9+
/\
/\
/\
2*30-
/\/\
/\/\
32-38-47-61-
/\/
69-79-81-
9
/\
/\
/\
230-
/\/\
/\/\
32-38-47-61-
/\/
69-79-81-
2
/\
/\
/\
9-30-
/\/\
/\/\
32-38-47-61-
/\/
69-79-81-
這樣就完成排序啦！
堆積排序法的程式實作
Rust
Java
Node.js
Go
///堆積排序法。
fnheap_sort_inner(array:&mut[i32],shift_down:&dynFn(&mut[i32],usize,usize)){
letlength=array.len();
letlength_dec=length-1;
forstartin(0..(length>>1)).rev(){
shift_down(array,start,length_dec);
}
foriin(1..length).rev(){
array.swap(0,i);
shift_down(array,0,i-1);
}
}
#[inline]
fnheap_sort_shift_down(array:&mut[i32],mutstart:usize,end:usize){
loop{
letleft=(start<<1)+1;
ifleft>end{
break;
}
letright=left+1;
letmax_child=ifright<=end&&array[right]>array[left]{
right
}else{
left
};
ifarray[start]>=array[max_child]{
break;
}
array.swap(start,max_child);
start=max_child;
}
}
#[inline]
fnheap_sort_desc_shift_down(array:&mut[i32],mutstart:usize,end:usize){
loop{
letleft=(start<<1)+1;
ifleft>end{
break;
}
letright=left+1;
letmin_child=ifright<=end&&array[right]
堆積排序法的複雜度
以#{{n}}#來表示要排序的資料筆數。
項目
值
備註
最差時間複雜度
#{{O(n\logn)}}#
最佳時間複雜度
#{{O(n)}}#
要排序的元素值都一樣時。
平均時間複雜度
#{{O(n\logn)}}#
最差空間複雜度
#{{O(1)}}#
是否穩定
否
SortingAlgorithm、排序演算法、堆積排序、HeapSort、完全二元樹、CompleteBinaryTree、最小堆積、MinHeap、MaxHeap、最大堆積
關於作者
MagicLen
各位好，我是MagicLen，是這網站的管理員。
我是台灣台中大肚山上人，畢業於台中高工資訊科和台灣科技大學資訊工程系，曾在桃機航警局服役。
我熱愛自然也熱愛科學，喜歡和別人分享自己的知識與經驗。
如果你有興趣認識我，可以加我的Facebook(點我)，並且請註明是從MagicLen來的。
載入中……
隨機文章
Rust程式語言如何將定數於編譯階段時串接成字串？
2020年9月3日
淺談媒介近用權─CH3有線電視公用頻道
2014年8月13日
Rust學習之路─第九章：錯誤處理
2018年6月19日
台北大縱走第一段：關渡─光武山─忠義山(嘎嘮別山)─向天池─向天山─面天山─二子坪
2020年7月24日
Rust程式語言可以單檔執行！如何把外部檔案和Rust程式編譯在一起？
2018年10月26日
免費訂閱本站電子報
交換連結
哈啦客談天說地
港澳資訊
電腦綠生活PCGreenLife
阿摩斯的小確幸
半熟態度-歐美加
英文練習網
低調一點
迴旋人生
iZO手札
冠均網頁設計公司
Bon部落網
坂本Sakamoto.blog-探究科技未知領域
FuYUan'sSpace
Mayday麥帶先生
程式的奇技淫巧之道
申請交換連結
申請交換連結
×
延伸文章資訊
- 1【資料結構和演算法】堆積, 堆積排序和優先佇列 - Jonny'Blog
而堆積排序是以堆積這個資料結構為基礎, 另外一個資料結構優先佇列也是以堆積為基礎的資料結構. 1. 定義. 定義1. (大根樹) 對於一棵樹, 若每一個節點的值 ...
- 21.4.2 Heap Tree - 資料結構&演算法筆記 - GitBook
定義: · 最小堆積(Min heap):父節點若小於子節點, 則稱之. · 最大堆積(Max heap):父節點若大於子節點, 則稱之. · 整理:.
- 3Heap結構的基本介紹與範例 - 筆記長也
Heap結構的基本介紹與範例. 2018-03-11 19:17:00 資料結構. Heap - 堆積. 堆積是一棵二元樹，其樹根大於子樹，且不管左右大小為何，這是與二元搜尋樹最大的差異。
- 4來征服資料結構與演算法吧| 搞懂Binary Heap 的排序原理
而Binary Heap 的種類分成兩種，分別為max-heap（最大堆積）和min-heap（最小堆積），max-heap 就是所有數字都大於它之下的數字。像上方的示意圖，不論是 ...
- 5[資料結構] 堆積(Heap) - iT 邦幫忙
[資料結構] 堆積(Heap) ... 堆積(Heap)，是一種特殊的完全二元樹，而堆疊不一樣，是完全不同的概念。 有分兩種，一種是最小堆積，另一種是最大堆積。
