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

$\endgroup$
  • 4
    $\begingroup$ How can an $n$-element heap have less than $n$ nodes? $\endgroup$ – Raphael Feb 9 '16 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 '16 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 '16 at 18:09
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

$\endgroup$
  • $\begingroup$ Right, but the proof does not have the -1. $\endgroup$ – leviless Feb 9 '16 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 '16 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 '16 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 '16 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}

$\endgroup$
  • $\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 at 14:44

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.