這里說的堆（heap）是一種 nearly complete binary tree：除了最低的一層外，其它層填充滿了結(jié)點(diǎn)，并且最底層的結(jié)點(diǎn)是從左到右填充的。

這里假定root結(jié)點(diǎn)的索引從1 開始。

它有如下的性質(zhì)：

1. 對于一個(gè)包含 n個(gè)元素的heap， 它的高度為 floor（lg n）

證明： 用 h表示這個(gè)heap的高度。則有：

2^h 《= n 《= 2^（h+1） -1 《 2^（h+1）

對上面取對數(shù)：

h 《 = lgn 《 h + 1

考慮到 h為整數(shù)， h只能是 floor（lg n）。

2. 對于以數(shù)組形式存儲的 n個(gè)元素的heap， 葉子結(jié)點(diǎn)的索引為 floor（n/2）+1， floor（n/2）+2， 。。.， n

證明： 假定葉子結(jié)點(diǎn)索引為 floor（n/2）， 那么， 2 * floor（n/2） 《 n， 表示這個(gè)葉子節(jié)點(diǎn)存在子結(jié)點(diǎn)。。，也就是它不是葉子結(jié)點(diǎn)。

2 * （floor（n/2）+1） =2 * floor（n/2） + 2 》 n， 不存在子節(jié)點(diǎn)，所以，索引為 floor（n/2）+1的結(jié)點(diǎn)是葉子結(jié)點(diǎn)。

3. n個(gè)元素的heap， 它的葉子結(jié)點(diǎn)的個(gè)數(shù)為 ceiling［n/2］

證明： 根據(jù) 2可以得出這個(gè)結(jié)論。

4. 對于 n個(gè)元素的heap， 最多有ceiling（n/2^（h+1））個(gè)高度為h的結(jié)點(diǎn)

證明 i： 用歸納法。

當(dāng) h = 0時(shí)的結(jié)點(diǎn)為葉子結(jié)點(diǎn)，根據(jù)3， 個(gè)數(shù)為 ceiling（n/2） = ceiling（n/2^（h+1）（當(dāng) h = 0）。

所以， h =0時(shí)成立。

假定 h-1時(shí)成立，那么此時(shí)高度 h-1的結(jié)點(diǎn)個(gè)數(shù)為 ceiling（n/2^（h-1））。

那么， 考慮去掉所有葉子結(jié)點(diǎn)的heap T‘。它的節(jié)點(diǎn)數(shù)為 n - ceiling［n/2］ = floor（n/2）。

在原來堆中高度為 h的結(jié)點(diǎn)在 T’中對應(yīng)的高度為 h-1.

那么在原來堆中高度h的結(jié)點(diǎn)的個(gè)數(shù)等于 T‘中高度為 h-1的個(gè)數(shù)：

ceiling（ floor（n/2）/2^（h-1）） 《= ceiling（（n/2）/2^（h-1）） = ceiling（n/2^h）。

證明 ii：

假定結(jié)點(diǎn) i高度為 h，那么， i， i*2， i*4， 。。.， i*2^h 為 i的最長路徑，并且 i*2^（h+1） 》 n.

于是有，

i*2^h 《= n 《 i * 2^（h+1）

i 》 n/2^（h+1）， i 《 2 * （n/2^（h+1））

所以， i的取值為， ceiling（n/2^（h+1））， ceiling（n/2^（h+1）） + 1， 。。.， ceiling（n/2^（h+1）） + ceiling（n/2^（h+1）） - 1

共有 ceiling（n/2^（h+1）） 個(gè)。