一文了解堆的性質(zhì)和證明

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

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

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

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

證明： 用 h表示這個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個元素的heap， 葉子結(jié)點的索引為 floor（n/2）+1， floor（n/2）+2， 。。.， n

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

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

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

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

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

證明 i： 用歸納法。

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

所以， h =0時成立。

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

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

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

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

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

證明 ii：

假定結(jié)點 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）） 個。