CS 14: Programming Assignment 2

Directory to submit: as2

Due date: Thursday Oct 19, 2000

Synopsis:

Write a class Heap that can be used to create and maintain a heap of integers, as well as sort those integers. Note that this class will be more complicated than simply implementing the various heap algorithms because you will need to worry about memory management and errors.

The class will include an Insert method so new values can be added to the heap. This presents a problem. If we put a limit on the size of the heap (i.e. by using a declaration such as int heap_array[ 100 ];), the insert will eventually fail. Of course, we can dynamically allocate the heap based on some initial size. Once the heap reaches that size and an insert is attempted, we can then simply allocate a new heap that is larger and copy the contents from the original heap. How much larger should the new heap be, though?

If we allocate a new heap that can hold only 1 more value, then the next time an insert is done, another new heap will need to be allocated. This will continue to be the case for every insert (unless values are also removed), which is very inefficient. However, if we allocate a heap that can hold double the number of current values, we might end up wasting a lot of memory if only a few more inserts are performed.

There is no easy solution to this problem, so our class will shift the responsibility to whoever uses the class. When a new Heap is created, an increment value will be included. Whenever the heap is full and needs to be reallocated, its size is increased by this value.

What kind of errors can occur? Dynamically allocating the heap might fail or there might be an underflow. In either case, our class will throw an exception. See the section on Handing Exceptions for details.

Details:

Your program will consist of 3 source files:

Heap.h (provided for you)
Heap.cc
main.cc

Heap.h:

This header file contains the complete heap class specification. This has been provided for you. Click here to see it. You must use this specification, though you are free to add to it if you wish. For example, you might want to add some type of print method to help in your testing.

Heap.cc

This is the file where the the class implementation should be placed. Specifically, the following methods must be written:

Heap constructors

The Heap class has 2 constructors.

The first constructor is passed 2 integer arguments, an initial size and an increment size. Both of these arguments should be checked to make sure they are larger than 0. If either arguments is 0 or less, an exception should be thrown. (See below for details on this.) The array_size and inc_size variables should be set to these argument values. This constructor should then allocate a new heap_array based on the initial size. If this allocation fails, an exception should be thrown. Because this array is initially empty, the heap_size variable should be set to 0.

The second constructor is passed an array of integers and 2 integer arguments; the size of the array and an increment size. If the array is NULL or either of the other arguments is 0 or less, an exception should be thrown. A new heap_array should be allocated based on the size of the passed array, the contents of the passed array should be copied to the heap_array, then the BuildHeap() method should be called (to make the heap_array into an actual heap). If allocating the heap_array fails, an exception should be thrown. The array_size and heap_size variables should both be set to the size of the passed array. The inc_size variable should be set to the increment size.

Heapify()

This method is passed an array, an index into that array that contains a value that may violate the heap property, and the size of the heap. It should re-establish the heap property in the array. It might seem as if the first and third parameter are not necessary since the class contains the heap_array and heap_size variables. However, HeapSort will also need to call this method, and it will be passing its own array and heap size.

Note that this method does not need to perform any error checking (i.e. a check to see if the array is NULL or the index is invalid). Why?

BuildHeap()

This method is called by the second constructor to convert an array of integers into a heap.

Insert()

This method is called to insert a new integer into the heap array. Note that if the heap_size is equal to the array_size, there is no more room in the array. In this case, a larger array needs to be allocated. It's size should be that of the current array plus the increment size (inc_size). The contents of the original array must be copied to the new array. The new array should then replace the original array.

This method should check that the heap array is not NULL and, if a new heap array needs to be allocated, that the allocation succeeded. If either of these are not true, an exception should be thrown.

ExtractMax()

This method should extract the largest integer from the heap array. If the heap array is empty, an exception should be thrown (this is an underflow).

Max()

This method should return the largest integer from the heap array. If the heap array is empty, an exception should be thrown (this is an underflow).

HeapSort()

This method should return a newly-allocated array containing the contents of the heap array sorted in ascending order. Note: the original heap array should not be modified. Instead, a new array should be allocated. If this allocation fails, an exception should be thrown. The function should also set the size parameter to the heap_size. Also, if the heap array is empty, an exception should be thrown. Note that this method will need to call Heapify().

main.cc

This file should contain your main() program. This program should fully test the functionality of the Heap class. Make sure to test both constructors. Make sure to test the case where the heap needs to be expanded. Make sure to test the case where you try to extract the maximum value from an empty heap. (This test list is not exhaustive.) Part of the grade for this project will be based on how well you test your class.

Handling Exceptions

Errors are handled in the Heap class member functions by throwing exceptions. To do this, use the following statement:

    throw exception();

In your main() program, when you call Heap functions, you must enclose these calls in try...catch blocks in order to catch any exceptions thrown. For example:

    Heap *heap = NULL;

    try
    {
        heap = new Heap( 10, 5 );
    }
    catch( exception e )
    {
        cout << "Creating the heap failed!\n";
        return 0;
    }

It is easier to understand exceptions by seeing them in action. I have written a short program that demonstrates them. Click here to see it. I recommend you download, compile, and run this program to better understand what it is doing.