二元堆積
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
二元堆積 | |||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
類型 | 二元樹/堆積 | ||||||||||||||||||||||||
發明時間 | 1964年 | ||||||||||||||||||||||||
發明者 | J·W·J·威廉斯 | ||||||||||||||||||||||||
用大O符號表示的時間複雜度 | |||||||||||||||||||||||||
|
二元堆積(英語:Binary heap)是一種特殊的堆積,二元堆積是完全二元樹或者是近似完全二元樹。二元堆積滿足堆積特性:父節點的鍵值總是保持固定的序關係於任何一個子節點的鍵值,且每個節點的左子樹和右子樹都是一個二元堆積。
當父節點的鍵值總是大於或等於任何一個子節點的鍵值時為「最大堆積」。當父節點的鍵值總是小於或等於任何一個子節點的鍵值時為「最小堆積」。
儲存
二元堆積一般用陣列來表示。如果根節點在陣列中的位置是1,第n個位置的子節點分別在2n和 2n+1。因此,第1個位置的子節點在2和3,第2個位置的子節點在4和5。以此類推。這種基於1的陣列儲存方式便於尋找父節點和子節點。
如果儲存陣列的下標基於0,那麼下標為i的節點的子節點是2i + 1與2i + 2;其父節點的下標是⌊floor((i − 1) ∕ 2)⌋。函式floor(x)的功能是「向下取整」,或者說「向下捨入」,即取不大於x的最大整數(與「四捨五入」不同,向下取整是直接取按照數軸上最接近要求值的左邊值,即不大於要求值的最大的那個值)。比如floor(1.1)、floor(1.9)都返回1。
如下圖的兩個堆積:
1 11 / \ / \ 2 3 9 10 / \ / \ / \ / \ 4 5 6 7 5 6 7 8 / \ / \ / \ / \ 8 9 10 11 1 2 3 4
將這兩個堆積儲存在以1開始的陣列中:
位置: 1 2 3 4 5 6 7 8 9 10 11 左图: 1 2 3 4 5 6 7 8 9 10 11 右图: 11 9 10 5 6 7 8 1 2 3 4
對於一個很大的堆積,這種儲存是低效的。因為節點的子節點很可能在另外一個主記憶體頁中。B-heap是一種效率更高的儲存方式,把每個子樹放到同一主記憶體頁。
如果用指標鏈結串列儲存堆積,那麼需要能訪問葉節點的方法。可以對二元樹「穿線」(threading)方式,來依序遍歷這些節點。
基本操作
在二元堆積上可以進行插入節點、刪除節點、取出值最小的節點、減小節點的值等基本操作。
插入節點
在陣列的最末尾插入新節點。然後自下而上調整子節點與父節點(稱作up-heap或bubble-up, percolate-up, sift-up, trickle up, heapify-up, cascade-up操作):比較當前節點與父節點,不滿足「堆積性質」則交換。從而使得當前子樹滿足二元堆積的性質。時間複雜度為。
刪除根節點
刪除根節點用於堆積排序。
對於最大堆積,刪除根節點就是刪除最大值;對於最小堆積,是刪除最小值。然後,把堆積儲存的最後那個節點移到填在根節點處。再從上而下調整父節點與它的子節點:對於最大堆積,父節點如果小於具有最大值的子節點,則交換二者。這一操作稱作down-heap或bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down,extract-min/max等。直至當前節點與它的子節點滿足「堆積性質」為止。
下屬對最大堆積的自上而下調整堆積的虛擬碼中,陣列A的下標索引值是從1開始:
Max-Heapify[1] (A, i):
left ← 2i
right ← 2i + 1
largest ← i
if left ≤ heap_length[A] and A[left] > A[largest] then:
largest ← left
if right ≤ heap_length[A] and A[right] > A[largest] then:
largest ← right
if largest ≠ i then:
swap A[i] ↔ A[largest]
Max-Heapify(A, largest)
構造二元堆積
一個直觀辦法是從單節點的二元堆積開始,每次插入一個節點。其時間複雜度為。
最佳演算法是從一個節點元素任意放置的二元樹開始,由下而上對每一個子樹執行刪除根節點時的Max-Heapify演算法(這是對最大堆積而言)使得當前子樹成為一個二元堆積。具體而言,假設高度為h的子樹均已完成二元堆積化,那麼對於高度為h+1的子樹,把其根節點沿著最大子節點的分枝做調整,最多需要h步完成二元堆積化。可以證明,這個演算法的時間複雜度為。
建造最大堆積的虛擬碼:
Build-Max-Heap[1] (A):
heap_length[A] ← length[A]
for i ← floor(length[A]/2) downto 1 do
Max-Heapify(A, i)
合併兩個二元堆積
最佳方法是把兩個二元堆積首尾相連放在一個陣列中,然後構造新的二元堆積。時間複雜度為,其中n、k為兩個堆積的元素數目。
如果經常需要合併兩個堆積的操作,那麼使用二項式堆積更好,其時間複雜度為。
參見
參考文獻
- ^ 1.0 1.1 Cormen, T. H. & al., Introduction to Algorithms 2nd, Cambridge, Massachusetts: The MIT Press, 2001, ISBN 0-07-013151-1
外部連結
- http://mathworld.wolfram.com/Heap.html(頁面存檔備份,存於網際網路檔案館)
- https://web.archive.org/web/20040611075754/http://www.policyalmanac.org/games/binaryHeaps.htm
|