For this assignment, you will add functionality to your CiscPriorityQueue that provides an in-place implementation of HeapSort. Our priority queue still implements the provided "CiscCollection" interface, which is a subset of java.util.Collection. The new methods are bold in the class description below. The only required, working content from the previous CiscPriorityQueue assignment is specified in the class description text, and consists of the instance variables, constructors, remove and compare methods (along with any other helper methods they may call).
| CiscPriorityQueue< E extends Comparable< E>> implements CiscCollection< E> |
| - elementData: E[] - comparator: Comparator< E> - size: int |
| + CiscPriorityQueue() + CiscPriorityQueue(comparator: Comparator< E>) + heapSort(unsortedArray: Comparable[], size: int): void - buildInPlaceHeap(unsortedArray: Comparable[], size: int): CiscPriorityQueue - sortInPlace(pq: CiscPriorityQueue): void - bubbleUp(): void + add(value: E): void + isEmpty(): boolean + peek(): E + remove(): E + size(): int + clear(): void + contains(value: Object): boolean + toArray(): Object[] + iterator(): Iterator< E> + toString(): String - contains(value: E, index: int): boolean - compare(item1: E, item2: E): int |
| CiscPriorityQueueIterator implements Iterator< E> |
| - index: int |
| + hasNext(): boolean + next(): E |
elementData : E[]
The array buffer into which the elements of the CiscPriorityQueue are stored.
comparator : Comparator< E>
The optional comparator object used to prioritize elements in the CiscPriorityQueue.
size : int
The number of elements in the CiscPriorityQueue.
CiscPriorityQueue()
Constructs an empty priority queue with an initial capacity of 10.
CiscPriorityQueue(comparator : Comparator< E>)
Constructs an empty priority queue with an initial capacity of 10 and assigns the provided Comparator to the comparator instance variable.
remove() : E
The remove() method should remove and return the element with the highest priority in the queue. If the queue is empty, it should throw a NoSuchElementException. The rightmost "leaf" in the max heap should become the new root then bubbled down to its final position. The priority queue should no longer store a reference to the removed element.
compare(item1 : E, item2 : E) : int
If the comparator instance variable is non-null, this private helper method should return the result of the comparator's compare method when passed item1 and item2 (respectively). If the comparator instance variable is null, this method should return the result of calling the compareTo method on item1 with item2 passed as an argument.
heapSort(unsortedArray : Comparable[], size : int) : void
This static method is called by a client to sort the provided "unsortedArray" parameter. The "size" parameter stores the number of elements in the unsortedArray. This method will need to call "buildInPlaceHeap" and "sortInPlaceHeap".
buildInPlaceHeap(unsortedArray : Comparable[], size : int) : CiscPriorityQueue
This private, static method creates a CiscPriorityQueue that uses the provided "unsortedArray" as its underlying array data structure. It will need to call bubbleUp, ensure that the size of the CiscPriorityQueue is updated, and return the CiscPriorityQueue it created.
sortInPlaceHeap(pq : CiscPriorityQueue) : void
This private, static method repeatedly removes an element from the CiscPriorityQueue and adds it back into the underlying array at the appropriate index.
bubbleUp() : void
This private method assumes that a new element to add to the heap exists at index "size". It repeatedly swaps that element with its parent until it is in a valid position in the heap.