Show that there are at most \(\lceil n/2^{h+1} \rceil\) nodes of height \(h\) in any \(n\)-element heap.
To understand this bound intuitively, think about the structure of a heap as a nearly complete binary tree. As you go higher up the tree (increasing height), the number of nodes at each height roughly halves. At height 0, you have many leaves (roughly \(n/2\)). At height 1, you have about \(n/4\) nodes. At height \(h\), you have roughly \(n/2^{h+1}\) nodes. The key question is: why is this upper bound tight for any heap with \(n\) elements?
The insight is that each node at height \(h\) is the root of a subtree containing at least \(2^h\) nodes (in the minimum case, a complete path down to a leaf). Since these subtrees are disjoint and together cannot exceed \(n\) nodes, we can bound how many such nodes can exist.
Proof by Induction
We prove by induction on \(h\) that an \(n\)-element heap has at most \(\lceil n/2^{h+1} \rceil\) nodes of height \(h\).
Base case: \(h = 0\) (leaves)
In any binary tree, the number of leaves is at most \(\lceil n/2 \rceil\). To see why, observe that in a complete binary tree:
- If \(n = 1\), there is 1 leaf, and \(\lceil 1/2 \rceil = 1\) ✓
- For \(n > 1\), every internal node has at least one child, so at least half the nodes must be leaves in a complete binary tree
More precisely, if there are \(\ell\) leaves and \(i\) internal nodes:
- Total nodes: \(n = \ell + i\)
- In a binary tree, internal nodes have 1 or 2 children
- In a complete binary tree (heap), all internal nodes except possibly one have exactly 2 children
- The number of children is \(\ell + i - 1\) (all nodes except the root are children)
- Since each internal node has at most 2 children: \(\ell + i - 1 \leq 2i\)
- This gives us: \(\ell \leq i + 1\)
- Therefore: \(\ell \leq (n+1)/2 = \lceil n/2 \rceil\)
So the base case holds: at most \(\lceil n/2 \rceil = \lceil n/2^{0+1} \rceil\) leaves.
Inductive step: Assume the claim holds for height \(h-1\), prove it for height \(h\).
Let \(N_h\) denote the number of nodes at height \(h\) in our \(n\)-element heap.
Each node at height \(h\) is the parent of at least one node at height \(h-1\) (otherwise, its height would be less than \(h\)). Conversely, each node at height \(h-1\) has exactly one parent.
In a binary tree, each node has at most 2 children. Therefore, each node at height \(h\) is the parent of at most 2 nodes at height \(h-1\).
Let \(N_{h-1}\) be the number of nodes at height \(h-1\). Then:
\[N_h \leq \lceil N_{h-1}/2 \rceil\]By the inductive hypothesis, \(N_{h-1} \leq \lceil n/2^h \rceil\). Therefore:
\[\begin{align*} N_h &\leq \lceil N_{h-1}/2 \rceil \\ &\leq \lceil (\lceil n/2^h \rceil)/2 \rceil \\ &\leq \lceil n/2^{h+1} \rceil \end{align*}\]The last inequality follows from the property that for any real number \(x\) and positive integer \(k\):
\[\lceil \lceil x/k \rceil / 2 \rceil \leq \lceil x/(2k) \rceil\]This completes the induction.
Alternative Proof Using Subtree Sizes
Here’s another way to see this result. Consider that each node at height \(h\) is the root of a subtree with at least \(2^h\) nodes. This is because:
- At height \(h\), there exists at least one path of length \(h\) from the node to a leaf
- In a complete binary tree, all levels except possibly the last are completely filled
- Therefore, the subtree has at least \(1 + 2 + 4 + \cdots + 2^{h-1} + 1 = 2^h\) nodes
Since the subtrees rooted at nodes of the same height are disjoint, and their union contains at most \(n\) nodes:
\[N_h \cdot 2^h \leq n\]Therefore:
\[N_h \leq n/2^h\]However, this gives us the weaker bound \(\lfloor n/2^h \rfloor\) rather than \(\lceil n/2^{h+1} \rceil\). The inductive proof above provides the tighter bound.