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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But the complete binary tree property states that the parent should have either 0 Or 2 children? Isn't it. $\endgroup$ – Sachin Bahukhandi Jun 19 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 at 12:05
  • $\begingroup$ Okay my bad. I misunderstood the concept. Sorry. And thank you for answering the question. $\endgroup$ – Sachin Bahukhandi Jun 19 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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