For this assignment, you will create a priority queue using a max heap, which means that the item with the largest value is at the top of the heap and values get smaller moving down the heap. Our priority queue implements the provided "CiscCollection" interface, which is a subset of java.util.Collection.
| CiscPriorityQueue< E extends Comparable < E >> implements CiscCollection< E > |
| - elementData: E[] - comparator: Comparator< E > - size: int |
| + CiscPriorityQueue() + CiscPriorityQueue(comparator: Comparator< E >) + 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.
add(value : E) : void
The add(E) method should add its parameter to the appropriate place in the queue. If space is unavailable for the value, it should first increase the capacity to double the current capacity plus 1. Values should be added as the rightmost leaf then bubbled up to their final position.
isEmpty() : boolean
The isEmtpy method should return true if priority queue is empty, false otherwise.
peek() : E
The peek() method should return the element with the highest priority in the queue. If the queue is empty, it should throw a NoSuchElementException.
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.
size() : int
The size method should return the number of elements in the priority queue.
clear() : void
The clear method should effectively empty the priority queue of all elements.
contains(value : Object) : boolean
The contains(E) method should return true if the given value is found in the queue. It should use its private helper method to search the queue recursively. Its implementation should stop searching a given subtree as soon as it is able to determine that the value cannot be present in that subtree.
toArray() : Object[]
Returns an array containing all the elements in the priority queue, as stored in the underlying array, starting with index 0. The length of the returned array is equal to the number of elements in the priority queue.
iterator() : Iterator< E >
The iterator method should create and return an instance of the CiscPriorityQueueIterator class that will be used to iterate through the elements in the priority queue.
toString() : String
The toString() method should return a string representation of the priority queue containing only actual values in the queue, in the format: "[10, 8, 9, 5, 3, 7, 2]" for a non-empty priority queue or "[]" for an empty priority queue.
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.
This class should be private (CiscPriorityQueue clients don't need to create instances of it directly) and non-static (it needs to access CiscPriorityQueue internals).
nextIndex : int
The index of the next element in the queue (if it exists) to be returned by the next call to next().
hasNext() : boolean
Returns true if the iterator has yet to return all data contained in the priority queue.
next() : E
Returns the next element in the priority queue, and updates nextIndex appropriately. Elements are returned in the order in which they are present in the priority queue's underlying array.