原文鏈接  點(diǎn)擊打開(kāi)鏈接

什么是堆

堆是一種特殊的二叉完全樹(shù)。堆的一個(gè)主要特點(diǎn)是它以一定的偏序（a partial order）來(lái)保存所有節(jié)點(diǎn)[譯者注：此處的偏序是指不完全的排序，堆只需要滿(mǎn)足父節(jié)點(diǎn)大于兩個(gè)子節(jié)點(diǎn)，而子節(jié)點(diǎn)之間沒(méi)有要求]。作為一顆完全樹(shù)，一層中的節(jié)點(diǎn)是從左到右填滿(mǎn)的。如果一個(gè)節(jié)點(diǎn)沒(méi)有左兒子，那么它一定沒(méi)有右兒子。并且在第h層中如果存在節(jié)點(diǎn)，那么第h-1層必須是填滿(mǎn)的。

以下是堆的正式定義（摘自Computer Algorithms by S. Baase and A. Van Gelder）：

一個(gè)二叉樹(shù)V是一個(gè)堆，當(dāng)且僅當(dāng)它滿(mǎn)足以下條件：

堆有兩種：最大堆和最小堆。最小堆中每個(gè)節(jié)點(diǎn)的優(yōu)先級(jí)小于或者等于它的子節(jié)點(diǎn)；最大堆則相反，每個(gè)節(jié)點(diǎn)的優(yōu)先級(jí)都大于或者等于它的子節(jié)點(diǎn)。

圖示最大堆（左）和最小堆（右）：

實(shí)現(xiàn)細(xì)節(jié)

CHeapTree類(lèi)通過(guò)一個(gè)數(shù)組，從上至下、從左至右地保存樹(shù)中的節(jié)點(diǎn)來(lái)實(shí)現(xiàn)堆。因此，上述圖示中的最大堆就可以表示為10,9,8,6,1,5。在這種表示方式中，第j個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)和父節(jié)點(diǎn)的表達(dá)如下（假設(shè)起始索引值是0）：

如果索引值越界，則該節(jié)點(diǎn)不存在。