- 前言
創作動機
寒假有點太混了，天天睡到中午 12 點，1 點才下床午餐，吃完就耍廢看片玩手遊到隔天。然後看了一下資工霸串，心中冒出一句：「幹 我到底在幹嘛==」，於是乎就有了這篇文，至少假裝一下我寒假有在做事 XD，就當成寒假作業吧。
- 什麼是 Heap (堆積)？
Heap 是一個樹狀的資料結構，並且為 Complete binary tree (完全二元樹)，這部分對樹狀沒有概念的人可以去 Hackerrank，把 tree 的 easy 難度的題目都寫過一遍，就算初步認識有關樹狀結構的程式碼了。什麼是完全二元樹呢？簡單來說，當所有的樹節點從上到下、從左到右都是連續填起來的，就是一個完全二元樹。這邊我可能講得不太好，我給個範例：
16 / \ / \ / \ / \ / \ / \ / \ 80 41 / \ / \ / \ / \ / \ / \ 32 82 95 35 / \ / \ / \ / \ 47 17 6 43 97 |
上圖就是一棵完全二元樹，依序節點可以從上到下、從左到右的表示為 16, 80, 41, 32, 82, 95, 35, 47, 17, 6, 43, 97，所以如果 6 那點葉節點刪掉的話，那麼這便不是棵完全二元樹；如果拿掉 97 那點葉節點的話，這仍然是棵完全二元樹，因為整棵樹仍然可以從上到下、從左到右的表示成 16, 80, 41, 32, 82, 95, 35, 47, 17, 6, 43。
所以 Heap 到底是什麼呢？當所有 Parent nodes (父節點) 全部都大於自己的 Child nodes (子節點) 時，且為一棵完全二元樹時，我們稱其為 max-heap，反之當所有 Parent nodes 全部都小於自己的 Child nodes 時，我們稱其為 min-heap。
(以下範例都使用 max-heap)
提供一個 max-heap 例子讓大家大概了解 heap 的概念，不去想程式碼的話，其實沒有很困難，用觀察就可以看懂了。
79 / \ / \ / \ / \ / \ / \ / \ 85 96 / \ / \ / \ / \ / \ / \ 67 91 3 17 / \ / \ / \ / \ 69 54 38 43 86 81 51 13 ↓ 把一棵完全二元樹轉成 max-heap 96 / \ / \ / \ / \ / \ / \ / \ 91 86 / \ / \ / \ / \ / \ / \ 69 85 81 51 / \ / \ / \ / \ 67 54 38 43 3 79 17 13 |
小提醒：依照每人的程式邏輯不同，heap 是可能有多種樣子的喔！
- 如何造 Heap？
第二種為向下檢查，從最後一個有子節點的父節點做向下檢查，如果子節點比父節點大，那麼就互換，並且再往下遞迴檢查，直到子節點都比父節點小就停住，繼續往前檢查一直到根節點。此方法需要知道所有的資料才能做，但是效率相對好。
我的程式碼採用向下檢查，反正沒有插入的情況，那麼用離線做法就行了。(好啦其實是我沒有寫向上檢查版本的 :D)
具體的過程和堆積木很像，從最後一個有子節點的父節點開始：
79 / \ / \ / \ / \ / \ / \ / \ 85 96 / \ / \ / \ / \ / \ / \ 67 91 3 17 / \ / \ / \ / \ 69 54 38 43 86 81 85 13 85 > 17 所以互換 79 / \ / \ / \ / \ / \ / \ / \ 85 96 / \ / \ / \ / \ / \ / \ 67 91 3 85 / \ / \ / \ / \ 69 54 38 43 86 81 17 13 86 > 3 所以互換 79 / \ / \ / \ / \ / \ / \ / \ 85 96 / \ / \ / \ / \ / \ / \ 67 91 86 85 / \ / \ / \ / \ 69 54 38 43 3 81 17 13 91 比自己子節點都大，不動 79 / \ / \ / \ / \ / \ / \ / \ 85 96 / \ / \ / \ / \ / \ / \ 67 91 86 85 / \ / \ / \ / \ 69 54 38 43 3 81 17 13 69 > 67 所以互換 79 / \ / \ / \ / \ / \ / \ / \ 85 96 / \ / \ / \ / \ / \ / \ 69 91 86 85 / \ / \ / \ / \ 67 54 38 43 3 81 17 13 96 比自己子節點都大，不動 79 / \ / \ / \ / \ / \ / \ / \ 85 96 / \ / \ / \ / \ / \ / \ 69 91 86 85 / \ / \ / \ / \ 67 54 38 43 3 81 17 13 91 > 85 所以互換 79 / \ / \ / \ / \ / \ / \ / \ 91 96 / \ / \ / \ / \ / \ / \ 69 85 86 85 / \ / \ / \ / \ 67 54 38 43 3 81 17 13 96 > 79 所以互換 往下遞迴檢查 86 > 79 所以互換 往下遞迴檢查 81 > 79 所以互換 以到葉節點 直接回傳 96 / \ / \ / \ / \ / \ / \ / \ 91 86 / \ / \ / \ / \ / \ / \ 69 85 81 85 / \ / \ / \ / \ 67 54 38 43 3 79 17 13 |
- 造 Heap 的程式碼
一般來說，初學比較不懂的可能是不知道要用什麼東西表示 heap，用普通陣列就行了，樹狀圖子父節點的關係我們是利用二元樹的 index (索引值) 特性，若從根節點開始下標 0，由上至下，由左至右依序為 1, 2, 3, 4, ..., n-1, n，那麼陣列 arr[k] 的子節點可以被表示為，arr[k*2 + 1] 和 arr[k*2 + 2]，而 arr[k] 的父節點則可以表示為 arr[(k-1) / 2]。這也是為什麼 heap 要是一個完全二元樹，如果中間有空缺的節點，就會造成效率低下，且無法構成 heap。
初學 heap 的人可能也有個疑問，為什麼 buildHeap 要從「最後一個有子節點的父節點」開始？
你可以由我上面的例子看出來，向下檢查就是檢查子節點有沒有比父節點大，有的話就子父節點互換，這邊就可以知道，既然葉節點沒有子節點那麼就沒有向下檢查的必要。
| /** * @param arr - The array that is going to be built as a heap. * @param n - The size of the array. * @param parent - The parent node index. */ void heapify(vector<int> &arr, int n, int parent) { int childLeft = parent*2 + 1; int childRight = parent*2 + 2; int greaterChild; if (childLeft >= n) { return; } if (childRight >= n || arr[childLeft] > arr[childRight]) { greaterChild = childLeft; } else { greaterChild = childRight; } if (arr[greaterChild] > arr[parent]) { swap(arr[greaterChild], arr[parent]); heapify(arr, n, greaterChild); } } /** * @param arr - The array that is going to be built as a heap. * @param n - The size of the array. */ void buildHeap(vector<int> &arr, int n) { for (int parent = (n-2)/2; parent >= 0; --parent) { heapify(arr, n, parent); } } |
- Heap sort (堆積排序)
1. 先把根節點和最後一個葉節點互換
2. 此時最後一個葉節點會是最大值 / 最小值，把它抽出到新的陣列
3. 由於現在根節點變動的關係，使得目前不是一個 heap，所以要對根節點做 heapify，讓整個樹再次變成 heap。
重複做 n 次，把整棵樹都拔光就可以得到排序好的新陣列了。下面給個執行範例，給不太懂得人看：
| 96 / \ / \ / \ / \ / \ / \ / \ 91 86 / \ / \ / \ / \ / \ / \ 69 85 81 85 / \ / \ / \ / \ 67 54 38 43 3 79 17 13 13 96 互換 把 96 移到新陣列 並且對根節點 13 做 heapify 91 / \ / \ / \ / \ / \ / \ / \ 85 86 / \ / \ / \ / \ / \ / \ 69 43 81 85 / \ / \ / \ / \ 67 54 38 13 3 79 17 此時已排序的陣列: {96} 91 / \ / \ / \ / \ / \ / \ / \ 85 86 / \ / \ / \ / \ / \ / \ 69 43 81 85 / \ / \ / \ / \ 67 54 38 13 3 79 17 17 91 互換 把 91 移到新陣列 並且對根節點 17 做 heapify 86 /\ / \ / \ / \ / \ / \ / \ 85 85 / \ / \ / \ / \ / \ / \ 69 43 81 17 / \ / \ / \ / \ 67 54 38 13 3 79 此時已排序的陣列: {96, 91} 86 /\ / \ / \ / \ / \ / \ / \ 85 85 / \ / \ / \ / \ / \ / \ 69 43 81 17 / \ / \ / \ / \ 67 54 38 13 3 79 79 86 互換 把 86 移到新陣列 並且對根節點 79 做 heapify 85 /\ / \ / \ / \ / \ / \ / \ 85 81 / \ / \ / \ / \ / \ / \ 69 43 79 17 / \ / \ / \ / \ 67 54 38 13 3 此時已排序的陣列: {96, 91, 86} 85 /\ / \ / \ / \ / \ / \ / \ 85 81 / \ / \ / \ / \ / \ / \ 69 43 79 17 / \ / \ / \ / \ 67 54 38 13 3 3 85 互換 把 85 移到新陣列 並且對根節點 3 做 heapify 85 / \ / \ / \ / \ / \ / \ 69 81 /\ /\ / \ / \ / \ / \ 67 43 79 17 / \ / \ / \ / \ 3 54 38 13 此時已排序的陣列: {96, 91, 86, 85} 85 / \ / \ / \ / \ / \ / \ 69 81 /\ /\ / \ / \ / \ / \ 67 43 79 17 / \ / \ / \ / \ 3 54 38 13 13 85 互換 把 85 移到新陣列 並且對根節點 13 做 heapify 81 / \ / \ / \ / \ / \ / \ 69 79 /\ /\ / \ / \ / \ / \ 67 43 13 17 / \ / \ / \ / \ 3 54 38 此時已排序的陣列: {96, 91, 86, 85, 85} 81 / \ / \ / \ / \ / \ / \ 69 79 /\ /\ / \ / \ / \ / \ 67 43 13 17 / \ / \ / \ / \ 3 54 38 38 81 互換 把 81 移到新陣列 並且對根節點 38 做 heapify 79 /\ / \ / \ / \ / \ / \ 69 38 /\ /\ / \ / \ / \ / \ 67 43 13 17 / \ / \ / \ / \ 3 54 此時已排序的陣列: {96, 91, 86, 85, 85, 81} 79 /\ / \ / \ / \ / \ / \ 69 38 /\ /\ / \ / \ / \ / \ 67 43 13 17 / \ / \ / \ / \ 3 54 54 79 互換 把 79 移到新陣列 並且對根節點 54 做 heapify 69 /\ / \ / \ / \ / \ / \ 67 38 /\ /\ / \ / \ / \ / \ 54 43 13 17 / \ / \ / \ / \ 3 此時已排序的陣列: {96, 91, 86, 85, 85, 81, 79} 69 /\ / \ / \ / \ / \ / \ 67 38 /\ /\ / \ / \ / \ / \ 54 43 13 17 / \ / \ / \ / \ 3 3 69 互換 把 69 移到新陣列 並且對根節點 3 做 heapify 67 / \ / \ / \ 54 38 / \ / \ 3 43 13 17 此時已排序的陣列: {96, 91, 86, 85, 85, 81, 79, 69} 67 / \ / \ / \ 54 38 / \ / \ 3 43 13 17 17 67 互換 把 67 移到新陣列 並且對根節點 17 做 heapify 54 / \ / \ / \ 43 38 / \ / \ 3 17 13 此時已排序的陣列: {96, 91, 86, 85, 85, 81, 79, 69, 67} 54 / \ / \ / \ 43 38 / \ / \ 3 17 13 13 54 互換 把 54 移到新陣列 並且對根節點 13 做 heapify 43 /\ / \ / \ 17 38 / \ / \ 3 13 此時已排序的陣列: {96, 91, 86, 85, 85, 81, 79, 69, 67, 54} 43 /\ / \ / \ 17 38 / \ / \ 3 13 13 43 互換 把 43 移到新陣列 並且對根節點 13 做 heapify 38 /\ / \ / \ 17 13 / \ / \ 3 此時已排序的陣列: {96, 91, 86, 85, 85, 81, 79, 69, 67, 54, 43} 38 /\ / \ / \ 17 13 / \ / \ 3 3 38 互換 把 38 移到新陣列 並且對根節點 3 做 heapify 17 / \ 3 13 此時已排序的陣列: {96, 91, 86, 85, 85, 81, 79, 69, 67, 54, 43, 38} 17 / \ 3 13 13 17 互換 把 17 移到新陣列 並且對根節點 13 做 heapify 13 / \ 3 此時已排序的陣列: {96, 91, 86, 85, 85, 81, 79, 69, 67, 54, 43, 38, 17} 13 / \ 3 3 13 互換 把 13 移到新陣列 並且對根節點 3 做 heapify 3 / \ 此時已排序的陣列: {96, 91, 86, 85, 85, 81, 79, 69, 67, 54, 43, 38, 17, 13} 3 / \ 3 3 互換 把 3 移到新陣列 並且對根節點 3 做 heapify 此時已排序的陣列: {96, 91, 86, 85, 85, 81, 79, 69, 67, 54, 43, 38, 17, 13, 3} |
- 其他
至於時間複雜度的話，詳細我不會算，但是由觀察的可以知道，總共迴圈要跑 n 次，每一次都要 heapify，而每次heapify都是兩邊挑一邊往下遞迴，最差會到 log(n) 次，所以時間複雜度大概是 O(n log(n))，跟 Merge sort (合併排序)、Quick sort (快速排序) 的時間複雜度相同，也算是高效排序法之一了。
不過我個人覺得應該一般上不太會用到這個排序法，主要是前面還要 build heap，需要消耗額外的時間，總體而言用途應該是不太大的。順帶一提，c++是有內建 make_heap() 和 sort_heap() 的，應該是在 <algorithm> 裡面的，平時要用就不用慢慢手刻了。
- Heap sort 總體程式碼
| /** * @param arr - The array that is going to be built as a heap. * @param n - The size of the array. * @param parent - The parent node index. */ void heapify(vector<int> &arr, int n, int parent) { int childLeft = parent*2 + 1; int childRight = parent*2 + 2; int greaterChild; if (childLeft >= n) { return; } if (childRight >= n || arr[childLeft] > arr[childRight]) { greaterChild = childLeft; } else { greaterChild = childRight; } if (arr[greaterChild] > arr[parent]) { swap(arr[greaterChild], arr[parent]); heapify(arr, n, greaterChild); } } /** * @param arr - The array that is going to be built as a heap. * @param n - The size of the array. */ void buildHeap(vector<int> &arr, int n) { for (int parent = (n-2)/2; parent >= 0; --parent) { heapify(arr, n, parent); } } /** * @param arr - The array that is going to be sorted. */ void heapSort(vector<int> &arr) { vector<int> sortedArr; int n = arr.size(); for (int i = 0; i < n; ++i) { print_tree(arr); swap(arr[0], arr[arr.size()-1]); sortedArr.push_back(arr[arr.size()-1]); arr.pop_back(); heapify(arr, arr.size(), 0); } arr = sortedArr; } int main() { const int n = 15; vector<int> arr = {79,85,96,67,91,3,17,69,54,38,43,86,81,85,13}; buildHeap(arr, n); heapSort(arr); return 0; } |
達人
