2
$\begingroup$

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 ?

  • 1
    Hint: prove that a complete binary tree of hight $h$ has $2^h$ elements2012-08-10
  • 0
    @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 .2012-08-10

2 Answers 2

2

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))$.

  • 0
    @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 .2012-08-10
  • 0
    @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?2012-08-10
  • 0
    I have posted [another question related to this here](http://math.stackexchange.com/questions/181022/worst-case-analysis-of-max-heapify-procedure) . can you try to clear my doubts on that too ?2012-08-10
4

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

  • 0
    Shouldn't that be $2^h-1$?2012-08-10
  • 0
    @Mike the number of internal nodes in a complete binary tree is 2^h-1 .2012-08-10
  • 0
    @Mike Yeah you are correct, actually i was thiking $\theta(2^h)$; anyway corrected it2012-08-10