資料結構大便當: Binary Heap

Kadai
Kadai
Jan 10, 2019 · 7 min read

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

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

Kadai

Written by

Kadai

A backend engineer in the real world.

More From Medium

Also tagged Computer Science

Also tagged Computer Science

Getting Started With Unix Domain Sockets

Apr 2 · 6 min read

Related reads

Also tagged Computer Science

Apr 2 · 7 min read

2

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade