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

- According to exercise 6.1-7, an \(n\)-element heap has exactly \(\lceil n/2 \rceil\) leaves.
- Notice that the nodes with height \(i\) become leaves after deleting all the nodes with height \(0,\cdots, i-1\).

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

## No comments:

Post a Comment