資料結構大便當: 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 的最大值
儲存
因為有了上述的特性,Heap 在實作上就可以用一個 list 來表示,由上到下,由左至右的排列在 list 中:
並且有一個重要的特性,可以找到 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 摟,近請期待。
感謝你/妳花時間讀這篇文章,如果你覺得這篇文章寫得不錯、有幫助到你,希望你能給我一點「拍手鼓勵」,也可以留言讓我知道你的想法,我會多加點油寫出更多內容的!
1. 拍「10下」:表示你喜歡這篇文章,謝謝你!
2. 拍「20下」:表示你覺得這篇文章很棒、願意分享給朋友!
3. 拍「30–40下」:希望未來我能寫更多這類主題的文章!
4. 拍好拍滿「50下」:給我最大的鼓勵,這將會支持我繼續寫作,並持續分享我的經驗!
拍手小秘訣: 只要將滑鼠(或手指)持續按著不放手掌的icon,就能夠連續拍手囉,試試看吧!