資料結構大便當： Binary Heap

binary heap 介紹與實作

大家好，我是 Kadai，資料結構大便當 EP.2 要說的是 binary heap，雖然早在上資料結構的時候就教過了，但一直以來對 binary heap 的用途跟特性都似懂非懂，所以決定趁這個機會好好再完整的學習一次 binary heap 的各種用途、特性和操作，當然最後也要實作一下啦。

簡介

Binary Heap 是在 1964 被 J. W. J. Williams 首次發表，是在 Heap Sort 上使用的資料結構，Binary Heap 有幾種特性：

• 每個 node 最多有兩個 child
• 同一階層要由左到右排列，不能跳過，eg: 下圖的底層 2, 7 一定要與 17 相連，如果要新增元素的話，因為 17 已經連滿，再來是要與 3 連，依序從左到右
• 如果是 max-heap 的話，每個 node 都要比自己 child 大，如果是 min-heap 反之（下圖是 max-heap）
• （max-heap）root 就會是整個 heap 的最大值

（max-heap）https://en.wikipedia.org/wiki/Heap_(data_structure)#/media/File:Max-Heap.svg

儲存

因為有了上述的特性，Heap 在實作上就可以用一個 list 來表示，由上到下，由左至右的排列在 list 中：

origin from: https://en.wikipedia.org/wiki/File:Heap-as-array.svg

並且有一個重要的特性，可以找到 left child node & right child node：

如果目前的 node 的 number 是 n：

• left child node 的 number 就是 2*n
• right child node 的 number 就是 2*n + 1

舉例來說，我們來看 node 19 的 number 是 2：

• left child node 17 的 number 就是 4
• right child node 12 的 number 就是 5

但因為寫程式的時候，index 是從 0 開始的，所以我們可以簡單做個轉換：

如果目前的 node 的 index 是 i：

• left child node 的 index 就是 2*i+1
• right child node 的 index 就是 2*i + 2

舉例來說，我們來看 node 19 的 index 是 1：

• left child node 17 的 index 就是 3
• right child node 12 的 index 就是 4

如果想要得到 parent node 也只要分辨出自己是 left or right child node 再回推就好了。

如此這般就可以快速得到 left & right child node 的 index 了！

Heap Sort 的步驟

接下來我們來說說要怎麼用 Heap 來做 sorting 吧，畢竟這就是他被發明出來的目的

首先，我們有一個 min-heap

然後我們把 root (3) pop 出來，放入一個 list 中，該 list 代表已經 sorted 好的元素：

然後現在 root 是空的，我們要把它重新整理成一個合法的 Heap，這一系列的步驟就叫做 Heapify：

首先我們把最後一個 node (7) 移到 root：

因為是 min-heap 所以移上來之後一定會比目前的 root 的 child node 大，，所以需要幫 node(7) 找合適的位子，我們的方法是，跟自己的 child node 做比較，把三個中最小的跟 root 做交換，重複做下去就完成了：

還不懂？看圖就對了！

node (5) / node (6) / node (7) 做比較，node (5) 移到 root

node (7) / node (16) / node (11) 做比較，node (7) 不用動，這樣就完成了

接下來只要重複做上面的步驟，直到所有的 node 都進入 sorted list 就可以完成 Heap Sort 了！

實作

好的，我們來把手弄髒吧！

實作 Heap & Heap Sort 主要分兩個部分：

• build a heap from an array
• do heap sort
  - pop root
  - heapify

這次我們使用 golang 來實作 Max-Heap，首先假設我們有一個 int array，我們要把他變成一個 Heap：

把它變成一個 Max-Heap 之後就可以開始做 Heap Sort 摟，這次我們挑戰做 in array 的 Heap Sort：

• 先新增一個 currLastNode 為最後一個元素的 index（currLastNode 代表 heap 在這個 array 裡面的範圍，剩下的代表排列完成的元素）
• 把取出的最大元素與最後一個元素作交換
• 把 currLastNode + 1
• 做 heapify
• 重複上述流程，就可以完成 Heap Sort 摟

全部的程式放在這邊喔：

https://github.com/kadai0308/data_structure/blob/master/heap/binaryHeap/main.go

Heap 的用途

是的，Heap 是被發明來做 Heap Sort 的，在 time complexity 有到達 O(nlog(n)) 但在實務上還是使用 quicksort 為主，為什麼呢，我會再寫一篇文章解釋，Heap 另外的重要用途還有作為實現 priority queue 的容器常與 Dijkstra’s algorithm 一起實作，另外也是解決 k-th largest problem 很實用的資結構。

後來也衍生了許多的變種，可以自己去查查各種變形的特性，蠻好玩的：

• Binomial heap
• fib heap
• pair heap
• leftist heap

後記

終於出了第二集了，超怕偷懶結果整個系列只有一篇文章哈哈，在實作的過程中也做了許多測試，最初的版本效能差到不行，果然光知道一個好的演算法或是資料結構是不夠的，還要搭配好的實作，才能完整發揮威力，最後還學到一些效能分析的工具，透過這個工具做了很大的優化，都可以在寫一篇工具介紹文了，總之，第二集就到這邊啦，下一集大便當可能就會轉移到 tree 或是 hash 摟，近請期待。

感謝你/妳花時間讀這篇文章，如果你覺得這篇文章寫得不錯、有幫助到你，希望你能給我一點「拍手鼓勵」，也可以留言讓我知道你的想法，我會多加點油寫出更多內容的！

Powered by Simon

1. 拍「10下」：表示你喜歡這篇文章，謝謝你！
2. 拍「20下」：表示你覺得這篇文章很棒、願意分享給朋友！
3. 拍「30–40下」：希望未來我能寫更多這類主題的文章！
4. 拍好拍滿「50下」：給我最大的鼓勵，這將會支持我繼續寫作，並持續分享我的經驗！

拍手小秘訣： 只要將滑鼠(或手指)持續按著不放手掌的icon，就能夠連續拍手囉，試試看吧！