[科普中國]-二叉堆

二叉堆是一種特殊的堆，二叉堆是完全二元樹（二叉樹）或者是近似完全二元樹（二叉樹）。二叉堆有兩種：最大堆和最小堆。最大堆：父結(jié)點(diǎn)的鍵值總是大于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值；最小堆：父結(jié)點(diǎn)的鍵值總是小于或等于任何一個(gè)子節(jié)點(diǎn)的鍵值。

存儲(chǔ)二叉堆一般用數(shù)組來表示。如果根節(jié)點(diǎn)在數(shù)組中的位置是1，第n個(gè)位置的子節(jié)點(diǎn)分別在2n和 2n+1。因此，第1個(gè)位置的子節(jié)點(diǎn)在2和3，第2個(gè)位置的子節(jié)點(diǎn)在4和5。以此類推。這種基于1的數(shù)組存儲(chǔ)方式便于尋找父節(jié)點(diǎn)和子節(jié)點(diǎn)。1

如果存儲(chǔ)數(shù)組的下標(biāo)基于0，那么下標(biāo)為i的節(jié)點(diǎn)的子節(jié)點(diǎn)是2i+ 1與2i+ 2；其父節(jié)點(diǎn)的下標(biāo)是?floor((i? 1) ∕ 2)?。函數(shù)floor(x)的功能是“向下取整”，或者說“向下舍入”，即取不大于x的最大整數(shù)（與“四舍五入”不同，向下取整是直接取按照數(shù)軸上最接近要求值的左邊值，即不大于要求值的最大的那個(gè)值）。比如floor(1.1)、floor(1.9)都返回1。

如下圖的兩個(gè)堆：

1 11 / \ / \ 2 3 9 10 / \ / \ / \ / \ 4 5 6 7 5 6 7 8 / \ / \ /\ /\ 8 9 10 11 1 2 3 4 將這兩個(gè)堆保存在以1開始的數(shù)組中：

位置: 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對于一個(gè)很大的堆，這種存儲(chǔ)是低效的。因?yàn)楣?jié)點(diǎn)的子節(jié)點(diǎn)很可能在另外一個(gè)內(nèi)存頁中。B-heap是一種效率更高的存儲(chǔ)方式，把每個(gè)子樹放到同一內(nèi)存頁。

如果用指針鏈表存儲(chǔ)堆，那么需要能訪問葉節(jié)點(diǎn)的方法?？梢詫Χ鏄洹按┚€”(threading)方式，來依序遍歷這些節(jié)點(diǎn)。

基本操作在二叉堆上可以進(jìn)行插入節(jié)點(diǎn)、刪除節(jié)點(diǎn)、取出值最小的節(jié)點(diǎn)、減小節(jié)點(diǎn)的值等基本操作。

插入節(jié)點(diǎn)在數(shù)組的最末尾插入新節(jié)點(diǎn)。然后自下而上調(diào)整子節(jié)點(diǎn)與父節(jié)點(diǎn)（稱作up-heap或bubble-up, percolate-up, sift-up, trickle up, heapify-up, cascade-up操作）：比較當(dāng)前節(jié)點(diǎn)與父節(jié)點(diǎn)，不滿足堆性質(zhì)則交換。從而使得當(dāng)前子樹滿足二叉堆的性質(zhì)。時(shí)間復(fù)雜度為 。

刪除根節(jié)點(diǎn)刪除根節(jié)點(diǎn)用于堆排序。2

對于最大堆，刪除根節(jié)點(diǎn)就是刪除最大值；對于最小堆，是刪除最小值。然后，把堆存儲(chǔ)的最后那個(gè)節(jié)點(diǎn)移到填在根節(jié)點(diǎn)處。再從上而下調(diào)整父節(jié)點(diǎn)與它的子節(jié)點(diǎn)：對于最大堆，父節(jié)點(diǎn)如果小于具有最大值的子節(jié)點(diǎn)，則交換二者。這一操作稱作down-heap或bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down,extract-min/max等。直至當(dāng)前節(jié)點(diǎn)與它的子節(jié)點(diǎn)滿足堆性質(zhì)為止。

構(gòu)造二叉堆一個(gè)直觀辦法是從單節(jié)點(diǎn)的二叉堆開始，每次插入一個(gè)節(jié)點(diǎn)。其時(shí)間復(fù)雜度為。

最優(yōu)算法是從一個(gè)節(jié)點(diǎn)元素任意放置的二叉樹開始，自底向上對每一個(gè)子樹執(zhí)行刪除根節(jié)點(diǎn)時(shí)的Max-Heapify算法（這是對最大堆而言）使得當(dāng)前子樹成為一個(gè)二叉堆。具體而言，假設(shè)高度為h的子樹均已完成二叉堆化，那么對于高度為h+1的子樹，把其根節(jié)點(diǎn)沿著最大子節(jié)點(diǎn)的分枝做調(diào)整，最多需要h步完成二叉堆化?？梢宰C明，這個(gè)算法的時(shí)間復(fù)雜度為O(n)。

合并兩個(gè)二叉堆最優(yōu)方法是把兩個(gè)二叉堆首尾相連放在一個(gè)數(shù)組中，然后構(gòu)造新的二叉堆。時(shí)間復(fù)雜度為，其中n、k為兩個(gè)堆的元素?cái)?shù)目。

如果經(jīng)常需要合并兩個(gè)堆的操作，那么使用二項(xiàng)式堆更好，其時(shí)間復(fù)雜度為。

參見最大—最小堆

本詞條內(nèi)容貢獻(xiàn)者為:

王沛 - 副教授、副研究員 - 中國科學(xué)院工程熱物理研究所