What are the minimum and maximum numbers of elements in a heap of height \(h\)?
To understand this problem, we need to think about what a heap of height \(h\) looks like. A heap is a nearly complete binary tree, meaning it’s completely filled on all levels except possibly the lowest, which is filled from the left.
The minimum number of elements occurs when we have just barely reached height \(h\). This happens when we fill all levels from 0 to \(h - 1\) completely, and then add just one element at level \(h\). A complete binary tree of height \(h - 1\) has \(2^h - 1\) elements (this is the sum \(1 + 2 + 4 + \ldots + 2^{h-1} = 2^h - 1\)). Adding one more element gives us a tree of height \(h\) with a minimum of \(2^h\) elements.
The maximum number of elements occurs when we fill all levels from 0 to \(h\) completely. This gives us \(1 + 2 + 4 + \ldots + 2^h = 2^{h+1} - 1\) elements.
Therefore:
- Minimum: \(2^h\) elements
- Maximum: \(2^{h+1} - 1\) elements