In order to find the recurrence function of The Height in Heap, the following figure is drawn.

enter image description here

Question 1: How can we compute the height if Right subtree in form of Log in base 3, and why do we have the height of Left subtree as log in base 3/2?

Question 2: it is stated that:
"for a complete binary tree to have the maximum height the last level should be half full."
i don't grasp the logic behind this line.why?

  • 1
    $\begingroup$ Welcome to CS.SE! Where are you quoting/excerpting this from? Can you provide additional context? It looks like you are taking an excerpt from some discussion, but we are forced to guess what the surrounding material is. Can you provide the full reasoning? What problem are they solving? How does this picture relate? $\endgroup$ – D.W. Mar 15 '17 at 16:45
  • 1
    $\begingroup$ For Q2, I think that maybe height is being mixed up with something else. The height of a tree is the longest distance from the root to a leaf node. It will be the same regardless of if a complete tree is full or not. $\endgroup$ – ryuu9187 Mar 15 '17 at 20:13

You are asking several question. I will only answer one. If you start with a set of size $n$ and you repeatedly reduce it to at most $rn$ elements, then after $t$ steps, you will have at most $r^tn$ elements. If $r^tn < 1$, then after $t$ steps you will have no elements. This happens for $t > \log_{1/r} n$. This explains where $\log_{3/2} n$ and $\log_2 n$ come from.

| cite | improve this answer | |

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.