堆積 Heap

刷題用過heap不少次，今天就來自己做做看。

堆積Heap

heap是一種基於類似二元樹的的資料結構，且是一顆complete binary tree，也就是除了最後一層以外都是滿的，而最後一層的節點都必須靠左。
以min heap為例，每個節點必須必須小於等於其子節點，所以根節點一定會是樹中最小值。

節點平衡分布，若有N個節點，樹的深度k為log N。
還有一個特點：若葉節點有i+1個，則非葉節點有i個。

基於陣列實作

雖然說是樹狀結構，但是可以用陣列來實現。
在寫線段樹的時候習慣以根節點編號1，左節點i*2，右節點i*2+1。但是python內建函數庫提到：

為了使得heap也能當作list使用，所以編號從0開始。左右節點分別為i*2+1和i*2+2
也可以保證遞增排序的list同時是合法的min heap 而heap的索引0就是根節點

加入新節點 Push

想要加入的值時，會把節點加在樹的末端。
如果新節點比父節點還小怎麼辦？這時就要進行上濾。

上濾 Sift Up

如果某節點x比父節點y還小，不符合min heap的規律，只要將兩者交換就好了！
交換後，又可能使節點y比更上層的父節點z還小，只要重複以上動作，直到根節點為止。
時間複雜度O(log N)。

取出最小值 Pop

刪除最小值(根節點後)，須把最末端的節點拿過來當作新的根結點。
同理，有可能破壞min heap的規律，這時候要進行下濾。

下濾 Sift Down

基本上就是上濾的反方向，差別在於子節點有兩個，要找到最小的那個，交換兩者，並繼續往下檢查，直到葉節點為止。 時間複雜度O(log N)。

堆化 Heapify

將整個陣列變成heap，只需透過數次下濾就可以達成，而不必排序！

剛才提到過：葉節點有i+1個，則非葉節點有i個。
那麼N=(2*i+1)，所以N節點的heap共有N/2個非葉節點。
注意索引編號是從0開始，所以0~(N/2)-1全是非葉節點。

我們只要倒序從(N/2)-1~0做下濾，就可以保證最小值浮到頂端。其實有點bubble sort的味道。

時間複雜度乍看是O(N log N)，但因為只有N/2的節點需要下濾1次，N/4的節點需要下濾2次…，1個節點下濾log N次。
計算下來其實是O(N)的時間，且不需要額外空間，空間複雜度O(1)。

其實使用上濾也可以堆化，但時間就是O(N log N)了。

程式碼

https://github.com/mocowcow/my-library/blob/master/pattern/heap.py

參考資料

https://blog.csdn.net/lighthear/article/details/79945528 https://www.cnblogs.com/wangchaowei/p/8288216.html https://github.com/python/cpython/blob/ce2383ec6665850a1bdffad388876481b6f3205f/Lib/heapq.py https://medium.com/@Kadai/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E5%A4%A7%E4%BE%BF%E7%95%B6-binary-heap-ec47ca7aebac