Java Reference
In-Depth Information
FIGURE 26-3
A revision of the steps shown in Figure 26-2, to avoid swaps
(a)
(b)
90
90
80
60
80
60
30
70
20
50
85
20
70
50
10
40
85
10
40
30
(c)
(d)
90
90
85
60
85
60
80
70
20
50
70
80
20
50
10
40
30
40
10
30
Figure 26-4 shows these same steps from the viewpoint of the array that represents the heap. In
Part
a
, which is analogous to Figure 26-3a, we note that we have room for a new entry at index 10.
The parent of this location is at location 10
/
2, or 5. We thus compare the new entry 85 to 30, the
contents of the location at index 5. Since 85
>
30, we move 30 to the location at index 10
(Figures 26-4b and 26-3b.) The remaining steps proceed in a similar fashion. Note that Figure 26-4d
corresponds to Figure 26-3c, and Figure 26-4f corresponds to Figure 26-3d.
26.7
The refined algorithm.
The following algorithm summarizes the steps that add a new entry to a
heap. Notice that the size of the array is expanded as necessary. To ignore the first location of the
array, we simply ensure that
parentIndex
is greater than 0.
Algorithm
add(newEntry)
if
(
the array
heap
is full
)
Double the size of the array
newIndex
= index of next available array location
parentIndex = newIndex/2
//
index of parent of available location
while
(parentIndex > 0
and
newEntry > heap[parentIndex])
{
heap[newIndex] = heap[parentIndex]
//
move parent to available location
//
update indices
newIndex = parentIndex
parentIndex = newIndex/2
}
//
place new entry in correct location
heap[newIndex] = newEntry
