Java Reference
In-Depth Information
figure 21.10
Creation of the hole at
the root
Min = 13
13
14
16
14
16
19
21
19
68
19
21
19
68
32
31
65
26
32
31
65
26
21.2.2
the
deleteMin
operation
Deletion of the min-
imum involves plac-
ing the former last
item in a hole that
is created at the
root. The hole is
percolated down
the tree through
minimum children
until the item can
be placed without
violating the heap-
order property.
The
deleteMin
operation is handled in a similar manner to the insertion opera-
tion. As shown already, finding the minimum is easy; the hard part is remov-
ing it. When the minimum is removed, a hole is created at the root. The heap
now becomes one size smaller, and the structure property tells us that the last
node must be eliminated. Figure 21.10 shows the situation: The minimum
item is 13, the root has a hole, and the former last item needs to be placed in
the heap somewhere.
If the last item could be placed in the hole, we would be done. That is
impossible, however, unless the size of the heap is two or three, because ele-
ments at the bottom are expected to be larger than elements on the second
level. We must play the same game as for insertion: We put some item in the
hole and then move the hole. The only difference is that for the
deleteMin
we
move down the tree. To do so, we find the smaller child of the hole, and if that
child is smaller than the item that we are trying to place, we move the child
into the hole, pushing the hole down one level and repeating these actions
until the item can be correctly placed—a process called
percolate down.
In
Figure 21.11, we place the smaller child (14) in the hole, sliding the hole
down one level. We repeat this action, placing 19 in the hole and creating a
new hole one level deeper. We then place 26 in the hole and create a new
The
deleteMin
operation is loga-
rithmic in both the
worst and average
cases
.
figure 21.11
The next two steps in
the
deleteMin
operation
14
14
16
19
16
19
21
19
68
21
19
68
31
32
31
65
26
32
65
26
Search WWH ::
Custom Search