1
$\begingroup$

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.

$\endgroup$

2 Answers 2

3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ But the complete binary tree property states that the parent should have either 0 Or 2 children? Isn't it. $\endgroup$ Jun 19, 2020 at 11:57
  • 1
    $\begingroup$ From Wikipedia: "In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible." Also in one of the source you have linked in your question it says "By the definition of a heap, all the tree levels are completely filled except possibly for the lowest level, which is filled from the left up to a point. " Could you please provide a reference to the definition of complete you are using? $\endgroup$
    – Steven
    Jun 19, 2020 at 12:05
  • $\begingroup$ Okay my bad. I misunderstood the concept. Sorry. And thank you for answering the question. $\endgroup$ Jun 19, 2020 at 12:25
1
$\begingroup$

I know there's already an accepted answer, but for those who've got the same question and are still a little bit confused (as I was), or sth is unclear, watch this crystal clear explanation till the end.

$\endgroup$
1
  • $\begingroup$ Those a little unsure better keep the applicable definition of heap handy. $\endgroup$
    – greybeard
    May 12, 2021 at 20:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.