Both classes that you are to define are to represent collections of Comparable elements, although neither one needs to implement the full Collection interface.

The Iterable class should provide a method insert(Comparable x), in addition to a 0-argument constructor that creates an empty collection, and to the methods of BidirectionalIterator. This class should also have a reset() method with void return type. If you do not attempt the extra credit, this method may simply do nothing.

The HeapColl class should provide methods isEmpty(), insert(Comparable), deleteMin(), and iterator, as well as a 0-argument constructor. The first three of these methods, and the constructor, should work as in the BinaryHeap class of the text. The iterator method should return a BidirectionalIterator, with properties as given above. For both classes, you are to assume that the iterator is initialized to the beginning of the sorted sequence. That is, initialation followed by repeated invocations of next() should visit elements in sorted order. You needn't worry about initializing the iterator to the end of the sorted sequence. You may ignore the possibility of heap overflow if you want.

Once an iterator is constructed for the HeapColl class, this iterator does not have to be aware of future insertions and deletions to the HeapColl. However the next() and previous() methods for the Iterable class should be able to visit all nodes currently in the collection. Another difference between the two classes is that the HeapColl class should allow multiple iterators, while the Iterable class has effectively only one iterator -- but one that takes O(1) time to create.

Your insertion methods should have average-case time complexity O(1). The next() and previous() methods should have worst-case time complexity O(log n). Deletion from a HeapColl should have worst-case time complexity O(log n). The hasNext() and hasPrevious() methods should have time complexity O(1). The iterator method of HeapColl should have worst-case time complexity O(n).
Hint: The iterator may be implemented by maintaining a maxheap and a minheap of small and large elements respectively. The next() and previous() methods would then just move an item from one heap to the other.

Feel free to use the BinaryHeap class of the text (with proper credit). As always, you may define additional classes or methods that you find helpful.

Use the class A3 to test your program. The class A3 and the interface BidirectionalIterator are available from the class web site.

For extra credit, have the Iterable.reset() method reset the iterator to the beginning of the sorted sequence of the Iterable object. This method should have time complexity linear in the size of the object.