Page 211 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes Figure 10.4 (a) illustrates the problem. The dequeueMin operation removes the key 2 from the
heap, but it is the node containing key 6 that must be removed from the tree to make it into a
complete tree again. When key 2 is removed from the root, a hole is created in the tree as shown
in Figure 10.4 (b).
The trick is to move the hole down in the tree to a point where the left-over key, in this case the
key 6, can be reinserted into the tree. To move a hole down in the tree, you consider the children
of the empty node and move up the smallest key. Moving up the smallest key ensures that the
result will be a min heap.
The process of moving up continues until either the hole has been pushed down to a leaf node,
or until the hole has been pushed to a point where the left over key can be inserted into the heap.
In the example shown in Figure 10.4 (b)-(c), the hole is pushed from the root node to a leaf node
where the key 6 is ultimately placed is shown in Figure 10.4 (d).
Program 10.4 gives the code for the dequeueMin method of the BinaryHeap class. This method
implements the deletion algorithm described above. The main loop (lines 15-25) moves the hole
in the tree down by moving up the child with the smallest key until either a leaf node is reached
or until the hole has been moved down to a point where the last element of the array can be
reinserted.
public class BinaryHeap
extends AbstractContainer
implements PriorityQueue
{
protected Comparable [] array;
public Comparable dequeueMin()
{
if (count == 0)
throw new ContainerEmptyException ();
Comparable result = array [1];
Comparable last = array [count];
--count;
int i = 1;
while (2 * i < count + 1)
{
int child = 2 * i;
if (child + 1 < count + 1
&& array [child + 1].isLT (array [child]))
child += 1;
if (last.isLE (array [child]))
break;
array [i] = array [child];
i = child;
}
array [i] = last;
return result;
}
// ...
}
Program 10.4: BinaryHeap class dequeueMin Method

206 LOVELY PROFESSIONAL UNIVERSITY