Is the heap in “Data Structures Algorithms in Java” by Goodrich, Tamassia, and Goldwasser missing sentinel leaves?

Question

In the book, Data Structures Algorithms in Java Sixth Edition by Goodrich, Tamassia, and Goldwasser on page 339, there is an

"Example of a heap storing 13 entries with integer keys. The last position is the one storing entry (13,W)."

I've recreated the a similar image using qtree-tikz with my own depth and height calculations in the box on the left.

According to the book,

A heap T storing n entries has height $h = \lfloor \log n \rfloor$.

Justification: From the fact that T is complete, we know that the number of nodes in levels $0$ through $h-1$ of T is precisely $1+2+4+...+2^{h-1} = 2^{h}-1$, and that the number of nodes in level $h$ is at least 1 and at most $2^h$. Therefore

$n \geq 2^h -1 +1 = 2^h$ and $n \leq 2^h -1 +2^h = 2^{h+1} -1$.

Here is where I see a problem. I added the depths and heights for nodes at each level according to my understanding of trees in the box to the left of the tree. The example tree Figure 9.1 shown above obviously has 7 inner nodes and although depth level 3 would have 8 nodes, it is unfull at 6 nodes.

If I follow the "Justification", I end up with the following

• "we know that the number of nodes in levels 0 through $h-1$ of T is $2^h-1$"

  $2^2 -1 = 3 \neq 7$.

• but my understanding is that the $7$ would match the formula $2^3-1$, which means the $h$ referred to in the text must be $h=4$. But the $h =3$ from my understanding. Herein lies the problem.

I am being forced to conclude that there must be a missing level of sentinels, $2^3 -1 = 7$ and the only way to get a power of 3 in those formulas is to have a height of 4. But why on earth would the authors, who otherwise explain everything in detail, not make important piece of information explicit? Or, did I miss something? I would appreciate a thorough explanation to help me understand the proof. It also seems that the authors throw around the term "level" loosely, sometimes meaning depth level and sometimes meaning height level.

I should also mention that earlier in the book, on page 286, they provide a definition for the height of a tree without any examples (and it is a bit cryptic).

We next define the height of a tree to be equal to the maximum of the depths of its positions (or zero, if the tree is empty).

• If $p$ is a leaf, then the height of $p$ is $0$.
• Otherwise, the height of $p$ is one more than the maximum of the heights of $p$'s children.

Answer 1

You have a tree made out of nodes at depths $0, 1, \ldots, h$ where $h$ is the height of the tree. The textbook is saying that the number of nodes at depths $0, \ldots, h - 1$ is equal to $2^h - 1$: notice the difference here between the $h-1$ and the $h$. This is easy to check by just looking at your picture, or using the formula for the sum of a geometric series:

$$ 2^0 + \cdots + 2^{h-1} = \frac{2^h - 1}{2 - 1} = 2^h - 1.$$

I think that a good rule of thumb for distinguishing between height and depth is that depth is the more useful one (the number of nodes on a complete level at depth $d$ is $2^d$, and a node's depth does not change as the tree grows), while the height $h$ is only really useful when looking at the tree as a whole (and is just the upper bound for depths).