证明二叉堆至少有一半的节点是叶节点

命题

二叉堆至少有 1/2 的节点是叶节点。

证明

首先,回顾哈 优先队列与堆 中讲述的二叉堆的结构性:二叉堆是一棵完全二叉树,即其元素总是从左到右一层一层填入,要么树被完全填满,要么就只有最底层未填满。

先证明对于理想二叉堆,该命题成立

令 a 为理想二叉堆的节点总数量,b 为叶节点的数量,h 为树的高度(注意,根节点的深度为 0)。每一层的节点数为 1, 2, 4, 8, …,很明显,这是一个等比数列,公比 q 为 2,首项为 1。

应用等比数列的求和公式可得到:

$ a = \frac{1-2^{h+1}}{1-2} = 2^{h+1}-1 $
$ b = 2^h $

进而 $ \frac{b}{a} = \frac{2^h}{2^{h+1}-1} > \frac{2^h}{2^{h+1}} $
而 $ \frac{2^h}{2^{h+1}} = \frac{1}{2} $
因此 $ \frac{b}{a} > \frac{1}{2} $。也就是说,对于理想二叉堆,命令成立。

再证明对于非理想二叉堆,该命题也成立

首先,将非理想二叉堆看作由两部分组成:

  1. 去掉最底层后的理想二叉堆
  2. 最底层,该层未填满。

令 a 为理想二叉堆的节点总数量,b 为理想二叉堆的叶节点数量,k 为最底层的叶节点数量。

因此节点总数为 $ a+k $;最底层的节点数为偶数时,叶节点数为 $ b+k-\frac{k}{2} = b+\frac{k}{2} $;为奇数时,叶节点数为 $ b+k-\frac{k+1}{2} = b+\frac{k}{2}-\frac{1}{2} $。

因为 $ \frac{b+\frac{k}{2}}{a+k} > \frac{b+\frac{k}{2}-\frac{1}{2}}{a+k} $
所以,只需要证明 $ \frac{b+\frac{k}{2}-\frac{1}{2}}{a+k} >= \frac{1}{2} $ 即可。

首先

\begin{array}{rcl}
\frac{b+\frac{k}{2}-\frac{1}{2}}{a+k} - \frac{1}{2}
&=& \frac{2b+k-1}{2(a+k)} - \frac{a+k}{2(a+k)}\\
&=& \frac{2b-a-1}{2(a+k)}\\
\end{array}

又有

\begin{array}{rcl}
\frac{b}{a} &>& \frac{1}{2} (前一小节已证明)\\
2b &>& a\\
2b-a &>& 0\\
\end{array}

因为 2b, a 都是正整数,所以 2b-a 也必然是整数。

进而 $ 2b-a > 0 $ 等价于 $ 2b-a \geq 1 $。

进而 $ \frac{2b-a-1}{2(a+k)} \geq 0 $,也就是 $ \frac{b+\frac{k}{2}-\frac{1}{2}}{a+k} - \frac{1}{2} \geq 0 $,即 $ \frac{b+\frac{k}{2}-\frac{1}{2}}{a+k} \geq \frac{1}{2} $。

因此,命题对于非理想二叉堆也成立。

0%