Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

From Heap Sort chapter of Introduction to algorithms :

Since a heap of n elements is based on a complete binary tree , its height is $\theta({lg}(n))$.

I know this is correct but how can this be proved ?

share|improve this question
1  
Hint: prove that a complete binary tree of hight $h$ has $2^h$ elements –  pritam Aug 10 '12 at 9:03
    
@pritam thats a pretty good way of coming to this conclusion . Can you throw an answer so that I can accept it as the accepted answer . –  Geek Aug 10 '12 at 9:11

2 Answers 2

up vote 1 down vote accepted

If we write down the series counting the number of elements at each level of the tree, then we get $$ \mbox{Number of elements} = n = 1 + 2 + 4 + 8 + ... + k \tag{1}$$ That is, at the first level, there is only one node, the root of the tree. At the second level are the root's two children. At the third, each of those two children's two children (making the total four at the third level). And so on until the last level, in which there are $k$ leaves of the tree.

$n$ is a finite geometric series whose first element is $a = 1$, ratio is $r = 2$. Using the formula for a geometric series, we get: $$ n = \frac{a(1 - r^i)}{1 - r} = 2^i - 1 $$ We seek $i$, which is the number of elements in the sequence given by $(1)$: $$ n = 2^i - 1 \Rightarrow i = \lceil\lg(n + 1)\rceil $$

This means there are $\lceil\lg(n + 1)\rceil$ levels in the tree, or $\lceil\lg(n + 1)\rceil$ terms in the series in $(1)$. The ceiling is required because nodes taking up part of a level warrant an extra count to the number of levels. We're interested in the height of the tree, not the number of levels. A keen observation will reveal that the height $h$ of a complete binary tree is one less than the number of levels. In other words, the height is the number of plus signs in $(1)$. So the height $h$ of a complete binary tree in terms of its $n$ elements is $$ h(n) = \lceil\lg(n + 1)\rceil - 1 \tag{2}$$

To show that $h(n) \in \Theta(\lg(n))$, first note the ceiling function will not affect the asymptotic behavior of $h(n)$, so the rounding up will be ignored for the rest of the discussion.

$h(n)$ is in $\Theta(\lg(n))$ if $$ \exists n_0 \in \mathbb{N},\; c_1, c_2 \in \mathbb{R},\; c_1, c_2 > 0 : c_1 \lg(n) \le \lg(n + 1) - 1 \le c_2 \lg(n), \quad \forall n \ge n_0 \tag{3}$$

For the lower bound, let $c_1 = \frac{1}{2}$. Then we have: $$\frac{1}{2}\lg(n) = \lg(\sqrt{n}) \le \lg(n + 1) - 1, \quad \forall n \ge 1 \tag{4}$$ In $(4)$, $n_0 = 1$.

For the upper bound, let $c_2 = 2$. We have: $$2\lg(n) = \lg(n^2) \ge \lg(n + 1) - 1, \quad \forall n \ge 1 \tag{5}$$ where $n_0 = 1$ here too.

So, for $c_1 = \frac{1}{2}$, $c_2 = 2$, and $n_0 = 1$, $(3)$ holds. Therefore $h(n) \in \Theta(\lg(n))$.

share|improve this answer
    
@ladadhini I changes my accepted answer as it has proved it rigorously . Can you explain a little bit more why the ceiling is required ?I guess the ceiling is required when it is near complete binary tree and not a complete binary tree ? Thanks . –  Geek Aug 10 '12 at 11:31
    
@Geek: Yes, you're on the right track, though a complete binary tree, despite its name, permits the last level to not be "full." The reason we must round up is the same reason we round up for the following situation: if a school bus has a capacity of 30 children, how many buses are need to transport 100 children? –  ladaghini Aug 10 '12 at 12:54
    
I have posted another question related to this here . can you try to clear my doubts on that too ? –  Geek Aug 10 '12 at 13:03

Using induction one can prove that a complete binary tree of hight $h$ has $2^h-1$ elements. So you have $n=2^h-1$, i.e. $h=\lg (n+1)=\theta(\lg n)$.

share|improve this answer
    
Shouldn't that be $2^h-1$? –  Mike Aug 10 '12 at 9:17
    
@Mike the number of internal nodes in a complete binary tree is 2^h-1 . –  Geek Aug 10 '12 at 9:21
    
@Mike Yeah you are correct, actually i was thiking $\theta(2^h)$; anyway corrected it –  pritam Aug 10 '12 at 9:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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