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

figure 21.22
Marking the first left
edge and the
subsequent right edge
for height 2 nodes
figure 21.23
Marking the first left
edge and the
subsequent two right
edges for height 3
nodes
figure 21.24
Marking the first left
edge and the
subsequent two right
edges for the
height 4 node
nodes, so this theorem implies that the sum is O ( N ). A more careful argument
establishes that the sum of the heights is N - v ( N ), where v ( N ) is the number
of 1s in the binary representation of N . A proof of this is left for you to do as
Exercise 21.12.