Show that the height of the heap is $\lfloor \lg n \rfloor$

Question

I want to show that a heap with $n$ elements has the height $ \lfloor \lg n\rfloor$.

That's what I have tried:

The "best" case is a complete binary tree,and then it is of the form:

So,the height is $k$,where $\sum_{i=0}^k 2^i=n \Rightarrow 2^{k+1}-1=n \Rightarrow k=\lg (n+1)-1$

The "worst" case is,when there is only one left child at the last level,so the tree is of the form:

So, the height is $k$,where $(\sum_{i=0}^{k-1} 2^i) + 1=n \Rightarrow \sum_{i=0}^{k-1} 2^i=n-1 \Rightarrow k=\lg n$

So, we have:

$$2^k \leq n \leq 2^{k+1}-1<2^{k+1} \Rightarrow k \leq \lg n<k+1$$

But ... how can I show now that $k= \lfloor \lg n \rfloor$ ?

Answer 1

You already have shown it!

You wrote it as

$$k \le \lg n < k+1,$$

so

$$\lg n = k + \alpha,$$

where

$$0 \le \alpha < 1,$$

thus

$$k = \lfloor \lg n \rfloor.$$

Answer 2

Consider a binary heap of height $h$ and let $n$ be the number of nodes. Looking at the definition of binary heap, it follows that it must have more than $$\sum_{i=0}^{h-1} 2^i = 2^{h} - 1$$ nodes, because every level from the first one until the second-last one is full. On the other hand, the last level is not full, so let $k$ be the number of leaves of the last level, it must be that $k \lt 2^{h}$. Therefore, we have that $$2^{h}-1 \lt n \lt 2^{h}-1+2^{h}$$ $$2^{h} \le n \lt 2^{h+1}$$ $$h \le \log_2n \lt h+1$$, which is the definition of floor of $ \log_2n$. Hence $ h = \lfloor \log_2 n \rfloor$.