算法导论6.33习题解答

CLRS 6.3-3 :

证明:在任一含n个元素的堆中,至多有[n/2^(h+1)]个高度为h的结点。

证明:

运用归纳证明

1.所有叶子结点的高度都为0,那么h = 0, [n/2^(h+1)] = [n/2],显然成立,因为叶子结点的序号是[n/2] + 1, [n/2] + 2, ..., n,见6.1-7的习题解答,http://www.cnblogs.com/shuaiwhu/archive/2011/03/20/2065081.html

2.若h = x时成立,则需证明h = x + 1也成立,易得证。

---
可以转载, 但必须以超链接形式标明文章原始出处和作者信息及版权声明
原文地址:https://www.cnblogs.com/null00/p/2065079.html