二叉堆積

二叉堆積
類型	二叉樹／堆積
發明時間	1964年
發明者	J·W·J·威廉斯
用大O符號表示的時間複雜度
演算法 平均 最差 空間 $O(n)$ $O(n)$ 搜尋 $O(n)$ $O(n)$ 插入 $O(1)$ $O(\log n)$ 尋找最小值 $O(1)$ $O(1)$ 刪除最小值 $O(\log n)$ $O(\log n)$

二叉堆積（英語：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操作）：比較當前節點與父節點，不滿足「堆積性質」則交換。從而使得當前子樹滿足二叉堆積的性質。時間複雜度為$O(\log n)$。

刪除根節點

刪除根節點用於堆積排序。

對於最大堆積，刪除根節點就是刪除最大值；對於最小堆積，是刪除最小值。然後，把堆積儲存的最後那個節點移到填在根節點處。再從上而下調整父節點與它的子節點：對於最大堆積，父節點如果小於具有最大值的子節點，則交換二者。這一操作稱作down-heap或bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down,extract-min/max等。直至當前節點與它的子節點滿足「堆積性質」為止。

下屬對最大堆積的自上而下調整堆積的偽代碼中，陣列A的下標索引值是從1開始：

Max-Heapify (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)

構造二叉堆積

一個直觀辦法是從單節點的二叉堆積開始，每次插入一個節點。其時間複雜度為$O(n\log n)$。

最佳演算法是從一個節點元素任意放置的二叉樹開始，由下而上對每一個子樹執行刪除根節點時的Max-Heapify演算法（這是對最大堆積而言）使得當前子樹成為一個二叉堆積。具體而言，假設高度為h的子樹均已完成二叉堆積化，那麼對於高度為h+1的子樹，把其根節點沿着最大子節點的分枝做調整，最多需要h步完成二叉堆積化。可以證明，這個演算法的時間複雜度為$O(n)$。

建造最大堆積的偽代碼：

Build-Max-Heap (A):
 heap_length[A] ← length[A]
 for i ← floor(length[A]/2) downto 1 do
 Max-Heapify(A, i)

合併兩個二叉堆積

最佳方法是把兩個二叉堆積首尾相連放在一個陣列中，然後構造新的二叉堆積。時間複雜度為$O(\log n\log k)$，其中n、k為兩個堆積的元素數目。

如果經常需要合併兩個堆積的操作，那麼使用二項式堆積更好，其時間複雜度為$O(\log n)$。

參見

• 最大—最小堆積

外部連結

• http://mathworld.wolfram.com/Heap.html（頁面存檔備份，存於互聯網檔案館）
• https://web.archive.org/web/20040611075754/http://www.policyalmanac.org/games/binaryHeaps.htm