6.1-2

6.1-2 Show that an n-element heap has height $\lfloor lg n \rfloor$. As we know the minimum and maximum no of elements for tree of height h is $2^h$ and $2^{h+1}-1$ $$ 2^h \leq n \leq 2^{h+1}-1 $$ $$ 2^h \leq n \leq 2^{h+1}-1 \lt 2^{h+1} $$ $$ 2^h \leq n \lt 2^{h+1} $$ applying logarithm for in equality $$ h \leq log n \lt h+1 $$ But h is an integer hence the height of the tree is $\lfloor lg n \rfloor$.