What are the minimum and maximum numbers of elements in a heap of height h?
-
29-09-2020 - |
Question
I came across the question:
What are the minimum and maximum numbers of elements in a heap of height $h$?
To which I came up with this theory: $$\sum_{i=0}^{h-1} 2^i = 2^h-1$$
$2^h-1$ is the internal nodes and that is understood according to the understood fact. But because nowhere except CLRS mentions heaps to be a Nearly Complete Binary Tree everywhere it is mentioned as a Complete Binary Tree.
The maximum number of elements can be easily computed: $$\sum_{i=0}^{h} 2^i = 2^{h+1}-1$$
But I cannot get the point of computing the minimum number of elements: Should it be: $$2^{h}+1$$ for $0$ or $2$ children property
Or should it be: $$2^{h}$$ for $0$ or $1$ children property
Reference1: https://walkccc.github.io/CLRS/Chap06/6.1/#61-1
Reference2: HeapSort
Thank you.
Solution
A heap of height $h$ is complete up to the level at depth $h-1$ and needs to have at least one node on level $h$.
Therefore the minimum total number of nodes must be at least $ \sum_{i=0}^{h-1} 2^i + 1 = 2^{h}-1 + 1= 2^h. $, and this tight since an heap with $2^h$ nodes has height $h$.