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