1
$\begingroup$

I am having trouble proving that an n-element heap can have at most $\lceil \frac{n}{2^{h+1}-1} \rceil$ nodes.

Please note that I am proving a loose bound.

First I proved that a complete binary tree can have at most $2^{h+1} - 1$ nodes. However, I don't know how to use this fact to inductively prove the formula above?

The only thing thus far in my inductive proof is showing the base case ($h=0$), which is trivial.

Improve this question
$\endgroup$
3
  • 4
    $\begingroup$ How can an $n$-element heap have less than $n$ nodes? $\endgroup$
    – Raphael ♦
    Feb 9, 2016 at 8:05
  • $\begingroup$ It simply cannot, but how could I show that in the inductive step. Could I just completely dodge an inductive proof and use a direct proof with this fact? $\endgroup$
    – leviless
    Feb 9, 2016 at 17:52
  • $\begingroup$ As long as your first line includes a false statement, you won't be able to find a proof. Be more careful about the details -- chances are that when you do that, proving things becomes much easier. $\endgroup$
    – Raphael ♦
    Feb 9, 2016 at 18:09

2 Answers 2

Reset to default
5
$\begingroup$

Probably, you mean this: A heap of size $n$ has at most $\lceil \frac{n}{2^{h+1}} \rceil$ nodes with height $h$.

Proof can be found for example here: http://www.cs.sfu.ca/CourseCentral/307/petra/2009/SLN_2.pdf

Improve this answer
$\endgroup$
4
  • $\begingroup$ Right, but the proof does not have the -1. $\endgroup$
    – leviless
    Feb 9, 2016 at 17:50
  • $\begingroup$ Because initial statement is incorrect (induction base). Check for example 3 - element heap. Floor layer contains obviously 2 nodes, but n / (2 ^(h + 1) - 1) for h = 0 is 3 / 1 = 3. $\endgroup$
    – Sukhanov Niсkolay
    Feb 9, 2016 at 18:31
  • $\begingroup$ The formula holds because the floor level can have at most 3 elements, yet it only contains 2. $\endgroup$
    – leviless
    Feb 9, 2016 at 18:51
  • $\begingroup$ No, heap should be a complete binary tree, otherwise time complexity analysis isn't working. Nevertheless if you don't require this property of heap, your statement is incorrect too, for example 12 node heap, where max is a root which have 10 children and one of the children have one child. Floor layer will have only one node, first layer will have 10 nodes, and second 1 node(root). So according to your formula for first layer: 10 / (2 ^ (1 + 1) - 1) == 4, but it's 10. $\endgroup$
    – Sukhanov Niсkolay
    Feb 10, 2016 at 12:35
-1
$\begingroup$

This is the actual question should be (Coreman 6.3-3) :A heap of size n has at most ⌈n/2^(h+1)⌉ nodes with height h.

This is just a simple intution for the proof.

This is an easy to prove property of complete binary tree/heap that is no. of leaf nodes = (total nodes in tree/heap)/2 {nearly}

Now, no. of nodes at height 0 = n/2 (because all leaf nodes are at maximum depth)

So traversing from bottom to top of tree, the height keep on increasing height by one, at each level we have no. of nodes = (no. of nodes from root to that level)/2, and once we finished counting that level we're left with same problem for half of the total node upto this level, for a level above (Think recursively, at each step although increasing the height, but deleting leaf nodes, and redoing the problem with 1/ of the nodes).

Therefore, no. of nodes at : At height 1 = (n/2)/2 = n/4, At height 2 = (n/4)/2 = n/8, . . . At height h = n/2^(h+1) {observing the trend}

Improve this answer
$\endgroup$
1
  • $\begingroup$ I don't see how this answers the question. $n/2+n/4+\dots+n/2^{h-1}$ is something like $n(1-1/2^{h+1})\approx n$ (I didn't check the exact power of $1/2$), which is seems different from the claim in the question. $\endgroup$
    – David Richerby
    Jul 17, 2019 at 14:44

Your Answer

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

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