二叉堆

二叉堆是一種特殊的堆，二叉堆是完全二元樹（二叉樹）或者是近似完全二元樹（二叉樹）。二叉堆有兩種：最大堆和最小堆。最大堆：父結點的鍵值總是大於或等於任何一個子節點的鍵值；最小堆：父結點的鍵值總是小於或等於任何一個子節點的鍵值。

基本介紹

• 中文名：二叉堆
• 外文名：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等。直至當前節點與它的子節點滿足堆性質為止。

構造二叉堆

一個直觀辦法是從單節點的二叉堆開始，每次插入一個節點。其時間複雜度為。

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

合併兩個二叉堆

最優方法是把兩個二叉堆首尾相連放在一個數組中，然後構造新的二叉堆。時間複雜度為，其中n、k為兩個堆的元素數目。

如果經常需要合併兩個堆的操作，那么使用二項式堆更好，其時間複雜度為。

參見

• 最大—最小堆