现在的位置: 首页 > 综合 > 正文

《算法导论（第2版）》习题6.3-3题解

2012年04月14日 ⁄ 综合 ⁄ 共 231字 ⁄ 字号小中大 ⁄ 评论关闭

Solution to CLRS 2e Exercise 6.3-3

Show that there are at most nodes of height h in any n-element heap.

A heap node of index i (starting from 1) is of height h if and only if , or $n / 2^{h + 1} < i <= n / 2^{h}$ , or $floor(n / 2^{h + 1}) < i <= floor(n / 2^h)$ since i is an integer. Therefore, the number of nodes of height h in any n-element heap is at most $floor(n / 2^h) - floor(n / 2^{h + 1}) <= ceil(n / 2^{h + 1})$ .