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\).