| |
The PriorityQueue Interface | page 7 of 9 |
A priority queue contains items ranked according to some relation of order and provides methods to add an item and to remove and return the smallest item. The items in a priority queue do not have to all be different; if several items have the smallest rank, the removal method can remove and return any one of them. In a Java implementation, we assume that the items are Comparable objects.
The Java library packages do not supply an interface specifically for priority queues. The PriorityQueue interface* shown below (PriorityQueue.java) defines four methods: isEmpty , add , removeMin , and peekMin . The methods in this interface are analogous to the ones in the Stack interface and the Queue interface.
public interface PriorityQueue
{
// Returns true if the number of elements in the
// priority queue is 0; otherwise, returns false
boolean isEmpty();
// obj has been added to the priority queue;
// number of elements in the priority queue is increased by 1
void add(Object obj);
// The smallest item in the priority queue is removed and
// returned; the number of elements in the priority queue
// is decreased by 1. Throws an unchecked exception if the
// priority queue is empty
Object removeMin();
// The smallest item in the priority queue is returned; the
// priority queue is unchanged. Throws an unchecked exception
// if the priority queue is empty
Object peekMin();
}
The Java Library does not supply a class that implements a priority queue. A simplistic class that implements a priority queue can be put together very quickly based on an ArrayList or LinkedList (for the full ArrayList implementation of a priority queue see ArrayPriorityQueue.java). However, a more efficient implementation can be developed based on heaps.
*Adapted from the College Board's AP Computer Science AB: Implementation Classes and Interfaces.
|