Why is the height of a heap defined as $\lg n$?

Question

I'm a bit confused about why the height of a heap (or a binary tree in general) is given by the floor of $\lg n$. E.g. if you have a tree with 7 nodes, you would get $h = 0$ instead of $h = 2$. Isn't $h$ the floor of $\log_2n$? I know it isn't since every book tells me otherwise, but I try to get why.

Answer 1

You are correct that the height of a heap is given by $\lfloor\log_2n\rfloor$. It is more than likely that the books you are looking at use $\lg n$ as shorthand for $\log_2 n$ rather than $\log_{10} n$.

Answer 2

In the context of data structures, $\log$ typically denotes the logarithm base $2$. In your example of a binary tree with $7$ nodes, we see that $\lfloor \log_2 (7) \rfloor = 2$.

More generally, consider a full binary tree with height $h$, where the root is at height zero. Then it has $\sum_{n=0}^h 2^n = 2^{h+1} - 1$ total nodes. It's easy to see that $\lfloor \log_2 (2^{h+1} - 1) \rfloor = h$, as desired.