A priority queue: the binary heap - Data Structures and Problem Solving Using Java - page 821

To obtain a linear-time bound for buildHeap , we need to establish that the
sum of the heights of the nodes of a complete binary tree is O ( N ). We do so in
Theorem 21.1, proving the bound for perfect trees by using a marking
argument.

We prove the
bound for perfect
trees by using a
marking argument.

For the perfect binary tree of height H containing N = 2 H + 1 - 1 nodes, the sum of the
heights of the nodes is N - H - 1 .

Theorem 21.1

Proof

We use a tree-marking argument. (A more direct brute-force calculation could also
be done, as in Exercise 21.10.) For any node in the tree that has some height h , we
darken h tree edges as follows. We go down the tree by traversing the left edge and
then only right edges. Each edge traversed is darkened. An example is a perfect tree
of height 4. Nodes that have height 1 have their left edge darkened, as shown in
Figure 21.21. Next, nodes of height 2 have a left edge and then a right edge dark-
ened on the path from the node to the bottom, as shown in Figure 21.22. In
Figure 21.23, three edges are darkened for each node of height 3: the first left edge
leading out of the node and then the two right edges on the path to the bottom.
Finally, in Figure 21.24 four edges are darkened: the left edge leading out of the root
and the three right edges on the path to the bottom. Note that no edge is ever dark-
ened twice and that every edge except those on the right path is darkened. As there
are ( N - 1) tree edges (every node has an edge coming into it except the root) and H
edges on the right path, the number of darkened edges is N - H - 1 . This proves the
theorem.

A complete binary tree is not a perfect binary tree, but the result we have
obtained is an upper bound on the sum of the heights of the nodes in a com-
plete binary tree. A complete binary tree has between 2 H

and 2 H + 1

- 1

figure 21.21
Marking the left
edges for height 1
nodes