CSC 212: Programming with Data Structures

Lab 9: Heaps

Due: Thursday, April 7, 11:59pm

Credit for this lab: Nick Howe

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. As you're working, write a short test program to try everything out.

For this lab, everyone should turn in their own code, but you are very welcome to discuss the code with a partner.

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:

  1. Create a heap myHeap, 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.

  2. Pop a few elements off the heap, and make sure that it is updated properly.

  3. 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 an in-place sort of an array, 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