資料結構大便當: 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 來做 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 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,就能夠連續拍手囉,試試看吧!

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store