Overview
For this lab, we'll be creating a new class called Heap. To avoid worrying about memory allocation issues, we will base the storage for our new class on the Java core class Vector. To start you off, here's a skeleton for a heap implementation, Heap.java. You'll need to fill in the definitions for some of the methods. When you are done, you will write a short test program to try everything out.
Part One
Some of the method definitions in Heap.java have been left empty. Your job is to fill in the implementations. Note that the comments in the function header tell you what each one should do, and sometimes give you some hints as to how to go about it.
Part Two
For this part of the lab, you will write a short test file called HeapTest.java that will test the class definitions we've been creating. This should do the following:
- Create a heap h, and insert about a dozen numbers, in no particular order. Print out the heap every so often so you can check that it is developing properly.
- Pop a few elements off the heap, and make sure that it is updated properly.
- Create an unsorted array of numbers. Loop over the array and add them all to an empty heap.
Then pop the numbers off the heap again, storing them all in the array backwards as you do so.
Finally, print out the array, which should now be sorted. (Note: You will loop over the array three times
in all: once to fill the heap, once to empty it, and once to print.) You may find it useful to use the
following syntax to create and initialize your array:
int arr[] = {-2,3,9,-7,1,2,6,-3};Note that this is not quite the in-place sort of an array we discussed in class, since the heap is not stored in the same memory space as the input array. If you want, you could write a static generic method that would perform an in-place heap sort on an array of Comparable. This is an optional extension of the lab.
To Submit
- Heap.java (as modified by you)
- HeapTest.java
- typescript