Show that an \(n\)-element heap has height \(\lfloor \lg n \rfloor\).
From Exercise 6.1-1, we know that a heap of height \(h\) contains at least \(2^h\) elements and at most \(2^{h+1} - 1\) elements. This gives us the relationship:
\[2^h \le n \le 2^{h+1} - 1\]Since \(2^{h+1} - 1 < 2^{h+1}\), we can strengthen the right inequality to get:
\[2^h \le n < 2^{h+1}\]Now we take logarithms (base 2) of all parts of the inequality:
\[\begin{align*} \lg(2^h) &\le \lg n < \lg(2^{h+1}) \\ h &\le \lg n < h + 1 \end{align*}\]This inequality tells us that \(\lg n\) lies in the interval \([h, h+1)\). In other words, \(h\) is the greatest integer less than or equal to \(\lg n\).
By definition, \(h = \lfloor \lg n \rfloor\).