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

the logarithmic bound to be a worst-case guarantee, the tree should be
balanced.

A complete binary tree is a tree that is completely filled, with the possible
exception of the bottom level, which is filled from left to right and has no
missing nodes. An example of a complete binary tree of 10 items is shown in
Figure 21.1. Had the node J been a right child of E, the tree would not be
complete because a node would be missing.
The complete tree has a number of useful properties. First, the height (long-
est path length) of a complete binary tree of N nodes is at most ⎣ log N ⎦ . The rea-
son is that a complete tree of height H has between 2 H and 2 H + 1 - 1 nodes.
This characteristic implies that we can expect logarithmic worst-case behavior
if we restrict changes in the structure to one path from the root to a leaf.

The heap is a com-
plete binary tree,
allowing represen-
tation by a simple
array and guaran-
teeing logarithmic
depth.

Second and equally important, in a complete binary tree, left and right links
are not needed. As shown in Figure 21.1, we can represent a complete binary tree
by storing its level-order traversal in an array. We place the root in position 1
(position 0 is often left vacant, for a reason discussed shortly). We also need to
maintain an integer that tells us the number of nodes currently in the tree. Then for
any element in array position i, its left child can be found in position 2 i . If this
position extends past the number of nodes in the tree, we know that the left child
does not exist. Similarly, the right child is located immediately after the left child;
thus it resides in position 2 i + 1. We again test against the actual tree size to be
sure that the child exists. Finally, the parent is in position .
Note that every node except the root has a parent. If the root were to have
a parent, the calculation would place it in position 0. Thus we reserve position
0 for a dummy item that can serve as the root's parent. Doing so can simplify
one of the operations. If instead we choose to place the root in position 0, the
locations of the children and parent of the node in position i change slightly
(in Exercise 21.15 you are asked to determine the new locations).
Using an array to store a tree is called implicit representation. As a result of
this representation, not only are child links not required, but also the operations

The parent is in
position

i /2 ⎦ , the
left child is in posi-
tion 2 i , and the
right child is in
position 2 i + 1 .

⎣

i ⁄ 2

Using an array to
store a tree is
called implicit
representation .

figure 21.1
A complete binary
tree and its array
representation

A

1

B C

2 3

D E F G

4 5 6 7

H I J

89 0

0 ABCDEFGH I J 11 12 13

0 1 2 3 4 5 6 7 8 9 10 11 12 13