## Thursday, February 10, 2011

### Nodes of height h in an n-element heap

This is exercise 6.3-3 of CLRS version 2.

Question:Show that there are at most $$\lceil n/2^{h+1} \rceil$$ nodes of height $$h$$ in any $$n$$-element heap.

Solution: First some facts
1. According to exercise 6.1-7, an $$n$$-element heap has exactly $$\lceil n/2 \rceil$$ leaves.
2. Notice that the nodes with height $$i$$ become leaves after deleting all the nodes with height $$0,\cdots, i-1$$.
Let $$y_i$$ be the total number of elements of the new tree after deleting all the nodes with height $$0,\cdots, i-1$$, and let $$x_i$$ be the number of leaves of the new tree. Then we have $$x_i = \lceil y_i/2 \rceil$$ by fact #1 and $$y_{i+1}=y_i - x_i$$ by fact #2. Thus we have $$y_{i+1} \leq y_i/2$$, and this leads to
$$y_i \leq n/2^i, \quad \forall n=0,1,\cdots.$$
The final conclusion follows from the relation $$x_i = \lceil y_i/2 \rceil$$.