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 :
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 :
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() :
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 :
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 :
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 :
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() :
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 :
This message was edited 1 time. Last update was at 05/11/2010 10:46:54
沒有留言:
張貼留言