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.

Was it helpful?

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

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top