Page 210 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS
P. 210
Unit 10: Heaps
10.2.4 Removing items from a Binary Heap Notes
The dequeueMin method removes from a priority queue the item having the smallest key. In order
to remove the smallest item, it needs first to be located. Therefore, the dequeueMin operation is
closely related to fi ndMin.
The smallest item is always at the root of a min heap. Therefore, the fi ndMin operation is trivial.
Program 10.3 gives the code for the fi ndMin method of the BinaryHeap class. Assuming that no
exception is thrown, the running time of fi ndMin is clearly O(1).
public class BinaryHeap
extends AbstractContainer
implements PriorityQueue
{
protected Comparable [] array;
public Comparable findMin ()
{
if (count == 0)
throw new ContainerEmptyException ();
return array [1];
}
// ...
}
Program 10.3: BinaryHeap class fi ndMin Method
Since the bottom row of a complete tree is filled from left to right as items are added, it follows
that the bottom row must be emptied from right to left as items are removed. So, you have a
problem: The datum to be removed from the heap by dequeueMin is in the root, but the node to
be removed from the heap is in the bottom row.
Figure 10.4: Removing an item from a Binary Heap
LOVELY PROFESSIONAL UNIVERSITY 205
