Number of nodes of given height in binary heap

Question

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

How can I show this? Or, how can I prove this?

Answer 1

Suppose towards a contradiction that your heap $H$ contains at least $\lceil n/2^{h+1} \rceil + 1$ nodes of height $h$, for some choice of $h$.

At least $\lceil n/2^{h+1} \rceil$ of these nodes are the roots of a complete binary subtree of the heap. Therefore each of these subtrees contains $\sum_{i=0}^h 2^i = 2^{h+1}-1$ nodes.

The subtree of $H$ rooted in any of the remaining nodes of height $h$, contains at least $1$ vertex (stronger lower bounds are possible, but this is all we need).

Since the subset of nodes having height at least $h$ in $H$ induces a binary tree $T$ whose leaves are the nodes of height exactly $h$ in $H$, we know that $T'$ must have at least $\lceil n/2^{h+1} \rceil + 1 - 1$ internal nodes. This means that the number of nodes of height larger than $h$ in $H$ is at least $\lceil n/2^{h+1} \rceil$.

Then, the total number $n$ of nodes in $T$ must be at least:

$$ \begin{align*} n \ge \lceil n/2^{h+1} \rceil \cdot (2^{h+1}-1) + \lceil n/2^{h+1} \rceil + 1 = \lceil n/2^{h+1} \rceil \cdot 2^{h+1} + 1 \ge n + 1. \end{align*} $$

This is a contradiction.