[ Data Structures with Java ] Section 22.5 : Implementing a Priority Queue

Preface :
In Chapter 15, we defined a priority queue and presented an application. The PQueue interface define the operations. Elements are added with a push() operation and are removed with a pop() operation. Elements in a priority queue have a priority status that dictates the order in which they exit the collection.
The HeapPQueue class implements the interface PQueue. As the name implies, the class uses a heap as the underlying storage structure. The user is free to specify either a Less or a Greater object, which dictates whether a deletion removes the minimum or the maximum element from the collection. By default, a HeapPQueue collection is a "maximum queue" and the element of highest priority is deleted by the pop() operation.

Implementing the HeapPQueue Class :
The HeapPQueue class uses a heap as the underlying storage structure. The private instance variable heapElt, is the array that contains the heap. A second instance variable, comp, is the Comparator object that indicates whether heapElt contains a maximum or minimum heap, and the integer numElts specifies the number of elements in the heap.
Two constructors create an empty HeapPQueue collection. One version takes a Comparator argument that dictates the type of heap. The default constructor uses the Greater comparator with a resulting maximum heap. In each case, the initial array has 10 elements. The following is a skeletal listing of the HeapPQueue class including an implementation of the default constructor :

- class HeapPQueue partly implementation :

view plaincopy to clipboardprint?

1. public class HeapPQueue implements PQueue{  
2.     private T[] heapElt;  
3.     private int numElts;  
4.     private Comparator comp;  
5.   
6.     public HeapPQueue(){  
7.         comp = new Less();  
8.         numElts=0;  
9.         heapElt = (T[]) new Object[10];  
10.     }  
11. ...  
12. }  

The HeapPQueue method peek() returns the element of highest priority. This is just the element in the array heapElt at index 0(the root). If the priority queue is emtpy, the method throws NoSuchElementException :

- Method peek() in class HeapPQueue :

view plaincopy to clipboardprint?

1. @Override  
2. public T peek() {         
3.     if(numElts==0) throw new NoSuchElementException("HeapPQueue pop(): empty queue");  
4.     return heapElt[0];  
5. }  

The push() and pop() methods check preconditions and then use the corresponding static methods in the Heaps class to maintain the heap. In the case of pop(), the implementation first checks for an empty priority queue and throws NoSuchElementException. Otherwise, it calls popHeap() with heapElt andnumElts as arguments. The heap has index range [0, numElts) in the array. After decrementing numElts, it returns the value obtained from popHeap() :

- Method pop() in class HeapPQueue :

view plaincopy to clipboardprint?

1. @Override  
2. public T pop() {  
3.     if(numElts==0) throw new NoSuchElementException("HeapPQueue pop(): empty queue");  
4.     T top = Heaps.popHeap(heapElt, numElts, comp);  
5.     numElts--;  
6.     return top;  
7. }  

The push() method calls pushHeap() to add an element. The method assumes that there are elements available at the tail of the array in which to grow the heap. This condition is not true when the size of the heap is the same as the size of the array. In this case, we must first increase the size of the array. The ArrayList class deals with this problem by increasing the capacity of the collection. The same algorithm is implemented by the private HeapPQueue method enlargeCapacity(), which doubles the current size of the array. A call to pushHeap() with argument for the array, the size of the heap, and the new item carries out the insert operation :

- Method push()/enalargeCapacity() in class HeapPQueue :

view plaincopy to clipboardprint?

1. protected void enlargeCapacity() {  
2.     T[] newTable = (T[]) new Object[heapElt.length*2+1];  
3.     for(int i=0; i
4.         newTable[i] = heapElt[i];  
5.     heapElt = newTable;  
6. }  
7.   
8. @Override  
9. public void push(T item) {  
10.     if(numElts == heapElt.length){enlargeCapacity();}//enlarge capacity  
11.     Heaps.pushHeap(heapElt, numElts, item, comp);  
12.     numElts++;  
13. }  

This message was edited 1 time. Last update was at 05/11/2010 10:46:54