一文了解堆的性質和證明

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

這里假定root結點的索引從1 開始。

它有如下的性質：

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

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

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

對上面取對數：

h 《 = lgn 《 h + 1

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

2. 對于以數組形式存儲的 n個元素的heap， 葉子結點的索引為 floor（n/2）+1， floor（n/2）+2， 。。.， n

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

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

3. n個元素的heap， 它的葉子結點的個數為 ceiling［n/2］

證明： 根據 2可以得出這個結論。

4. 對于 n個元素的heap， 最多有ceiling（n/2^（h+1））個高度為h的結點

證明 i： 用歸納法。

當 h = 0時的結點為葉子結點，根據3， 個數為 ceiling（n/2） = ceiling（n/2^（h+1）（當 h = 0）。

所以， h =0時成立。

假定 h-1時成立，那么此時高度 h-1的結點個數為 ceiling（n/2^（h-1））。

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

在原來堆中高度為 h的結點在 T’中對應的高度為 h-1.

那么在原來堆中高度h的結點的個數等于 T‘中高度為 h-1的個數：

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

證明 ii：

假定結點 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）） 個。