Java Reference
In-Depth Information
26.5
The basic algorithm.
The algorithm to add an entry to a heap is not difficult. Recall that in a max-
heap, the object in a node is greater than or equal to its descendant objects. Suppose that we want to
add 85 to the maxheap in Figure 26-1. We first would place the new entry as the next leaf in the
tree. Figure 26-2a shows that we add 85 as a left child of the 30. Notice that we actually would
place 85 at index 10 of the array in Figure 26-1b.
Figure 26-2a is no longer a heap, since 85 is out of place. To transform the tree into a heap, we let
85
float
up
to its correct location. Since 85 is larger than its parent, 30, we swap it with the parent, as
Figure 26-2b shows. The 85 is still larger than its new parent, 80, so we swap again (Figure 26-2c).
Now 85 is less than its parent, so we have transformed the tree in Figure 26-2a into a maxheap.
FIGURE 26-2
The steps in adding 85 to the maxheap in Figure 26-1a
(a)
(b)
(c)
90
90
90
80
60
80
60
85
60
70
30
20
50
85
20
50
80
20
50
70
70
40
40
40
30
10
85
10
30
10
Question 2
What steps are necessary to add 100 to the heap in Figure 26-2c?
26.6
Avoiding swaps.
Although the swaps mentioned in the previous segment make the algorithm easier
to understand and to describe, they require more work than is actually necessary. Instead of placing
the new entry in the next available position within the tree, as we did in Figure 26-2a, we need only
reserve space for it. In an array-based implementation, we simply check that the array is not full.
Figure 26-3a shows the new child as an empty circle.
We then compare the new entry—the 85 in this example—with the parent of the new child.
Since 85 is larger than 30, we move the 30 to the new child, as Figure 26-3b shows. We treat the
node that originally contained 30 as if it were empty. We now compare 85 with the parent, 80, of
the empty node. Since 85 is larger than 80, we move the 80 to the empty node, as Figure 26-3c
shows. Since 85 is not larger than the next parent, 90, we place the new entry into the empty node,
as Figure 26-3d shows.
Note:
To add a new entry to a heap, you begin at the next available position for a leaf.
You follow a path from this leaf toward the root until you find the correct position for the
new entry. As you do, you move entries from parent to child to ultimately make room for
the new entry.
