3
$\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 ?

  • 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
    I have posted [another question related to this here](http://math.stac$k$exch$a$nge.com/questions/181022/worst-case-analysis-of-max-hea$p$ify-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
    @Mike Yeah you are correct, actually i was thiking $\theta(2^h)$; anyway corrected it2012-08-10