For this assignment, you are to complete the implementation of a minimum-oriented heap with handles. You will use this heap in a future assignment, so be sure to complete the assignment successfully. This is a straightforward task, and much of the pseudocode for what you need to do is in the book, though within a slightly different structure. You are expected to document your code, and to give running times in the places specified.
A handle in a heap gives the index in the heap array at which a heap element is stored. If the value of the element's key is changed, that might affect the heap order at that element's location. The element's handle lets us call heapifyUp or heapifyDown (depending whether the value is decreased or increased) at the right point in the heap array to restore heap order. Handles thus allow us to maintain our heap in the presence of changing data.
For this assignment, implement your heap in Java. To get you started, we've provided a skeleton for Heap.java.
The Java version of the heap takes in objects of type HeapElt, which is a very basic class that is easily extended to allow you to store integers, vertices, or whatever other sort of Comparable object you want. We've provided both the HeapElt.java file for the HeapElt class, and the file HeapInt.java containing code for its extension to the HeapInt class.
The test program for this assignment changes the keys of elements in your heap (see below for an explanation of what handles are for). This requires a method setKey(), which is included in the HeapInt class.
There is also TestHeap.java, that provides s program you can use to test your implementation.
A word of warning: The test program passes object references to the heap. The objects themselves are kept by the test program in a certain order, and are referenced by the test program at various points. Writing heap code that makes copies of the objects or that swaps values between objects is incorrect, and will lose points. Move references around in your heap. Write handle information into the objects when necessary, but do not otherwise modify the objects in the test program.
All these files are available in the directory ~csci311/HW02. Do not change any method or data member names provided.
Most of this assignment is straightforward and based on lecture material. However, note that you are to implement a minimum heap (one that has the minimum value at the root of every subtree rather than the maximum). Also, you must make your heap work with handles. A handle in this case is the index at which the reference to a specific object is stored in the heap array. Note that every HeapElt object, and thus every item stored in the heap, has a data member named handle in which its handle is stored. Each time that a heap method changes the location (i.e., the position in the heap array) of a reference to an item, that item's handle should be updated to reflect its current position in the heap. Note that the Heap class has a method exchange() that swaps elements (i.e., references to record objects) in the heap array. If you make all moves using this method, you can make all changes to handles in this method as well. (As far as handles go, there is one additional issue: When and where does an object's handle initially get set?)
Also note that the program provided
allows the heap to grow dynamically as items are inserted (i.e.,
there is no hardcoded limit on the size of the heap). The
standard way of doing this is to double the size of the heap when it
becomes full (typically this is done when inserting an item for which
there is no room). You will need to implement the doubleHeap() method, which
allocates a new array, copies the values from the array datamember to it,
and assigns
the new array to the array data member. The initial array size when the
heap is constructed is 4, which is artificially small so you can test if
your implementation deals with growing the heap correctly. Do not change
this and make a bigger array to avoid having to double.
Where in the program will doubleHeap() be called? Under what circumstances?