Watch this space for later updates.
[11/1]- A graphical test program has been created for use with your HeapPQ class. Download this file, unzip it, and read the README.TXT on how to use it
You are to create a class HeapPQ that implements the PriorityQueue interface. The PriorityQueue interface extends the java.util.Collections interface by adding the operations getFirst(), removeFirst() and comparator(). The goals for this homework are (1) to learn how to implement a priority queue using a heap and (2) to learn how to make your own extensions to the Java Collections Framework.
We plan to grade the homework based on your electronic submission. The hardcopy is required mainly for backup.
Create a class called HeapPQ that implements the PriorityQueue interface. Note that a PriorityQueue allows duplicates (this is why PriorityQueue extends Collection and not SortedSet).
Much of the work is actually done for you. Java provides an abstract class (java.util.AbstractCollection) that is meant to be extended when a new type of Collection is implemented. AbstractCollection contains implementations of most of the Collection methods; there are just a few methods that you must provide. (Note that there are similar classes provided for creating new kinds of sets, lists, and maps: AbstractSet, AbstractList, AbstractSequentialList, and AbstractMap. These other abstract classes are not needed for this assignment.)
Read the documentation for AbstractCollection in the online Java API. It explains that AbstractCollection implements most of the Collection methods, so it is not necessary to implement them in your own extension-to-collection except for reasons of efficiency. According to the documentation, you must implement only size() and iterator(). This will result in an unmodifiable collection. If you want to allow modifications then you must implement add() and the iterator's remove() method.
You can look at the documentation for each method of AbstractCollection to see an explanation of how that method is implemented. This provides enough information to discover which methods use add() and which ones use the iterator's remove() method. It turns out that if you don't implement the iterator's remove() method then remove(), removeAll(), retainAll(), and clear() (all inherited from Collection) will fail to work (i.e., will throw an UnsupportedOperationException). For a PQ this is OK. Except for clear(), these would be unusual operations for a PQ anyway. We do want to have clear() though, so you will need to write a clear() method to override the one provided by AbstractCollection.
Thus, to make our extension to AbstractCollection work correctly, we need to implement size(), iterator() (returning an iterator without remove()), add(), and clear(). In addition, we need to implement some constructors, and those operations that are needed by a PriorityQueue (getFirst(), removeFirst(), and comparator()).
In summary, the methods that you must implement for this assignment are
The various constructors are needed so that this new type of collection has constructors similar to those available for other Collections classes. Note that your HeapPQ should use the natural order of its items unless the second (comparator-using) constructor is used. If a comparator is given then the order of items in the priority queue should correspond to the order produced by the comparator. The third constructor (the one that loads the heap from an existing collection) can be written to run in O(n) time, but an O(n log n) algorithm is acceptable.
The iterator that you return should be an iterator that does not allow the remove() operation. There are two ways to ensure that this occurs: (1) build you own iterator or (2) find a simple way to return an iterator that disallows remove() (hint: look at Collections.unmodifiableList() and related methods). If you wish, you may return an iterator that does allow remove, but if you do this, make sure that the heap is properly repaired after the removal.
Note that your iterator must report items in the order in which they are stored in the heap (i.e., in order of index). This is not really necessary for the HeapPQ to work as a priority queue, but it is necessary for purposes of grading: we need to see how items are arranged in your heap. This ordering should also be useful for your own debugging.
Your class HeapPQ should implement the interface PriorityQueue.java. PriorityQueue.java should not be changed.
The text provides code for a heap, but the implementation details are different enough (the text does not use the Collections Framework) that, if you understand how a heap works, it is probably more efficient to write your own code from scratch. For instance, the text does its own array-doubling, but a better option is to store the heap in an ArrayList; thus, you can have array-like access to the elements without having to write your own array-doubling code.
Note that a List starts at index 0 while heaps are generally presented as starting at index 1. The solution chosen by the text is to simply not use the entry at index 0. This solution is acceptable, but be careful; you need to make sure that the iterator returned by iterator() starts at the first heap item. The other possible solution is to use slightly different rules for computing lchild, rchild, and parent. What should the rules be if we start at index 0 instead of index 1?
Be sure to repair the heap when add() or removeFirst() are used. If you first write code for the helper methods bubbleUp(int i) and bubbleDown(int i) then the code you need to write for add() and removeFirst() should be short. (In the text these helper methods are called percolateUp() and percolateDown().)
It is useful to create some helper methods. The methods bubbleUp() and bubbleDown() are mentioned above. Other possible useful methods include a compare method that compares two items using either the natural ordering or the saved comparator as appropriate, and a swap method that swaps two items in a list given the list-indices.
Write a main() method for your HeapPQ class. We aren't grading you on this method, but this makes a good place for you to put code for testing your HeapPQ. The classes java.lang.Integer and java.lang.String are both Comparable so these make easy types to use in your test code. Also, java.lang.String provides a Comparator (CASE_INSENSITIVE_ORDER) that you can try. Be sure to test your code for the case in which the last item is removed from the heap.