The author's code for binary heaps has a number of unacceptable limitations for a class that is to be used by other programmers. One limitation is the fixed size for the heap. A second is the requirement for an overloaded Min_Val function. This lab examines ways to improve the class design and extend its usefulness.

1. Copy the files
   • /dept/cs/cs230/www/labs/lab8/heap.h
   • /dept/cs/cs230/www/labs/lab8/main.cpp
   and create a new project which incorporates them.

2. The Binary_Heap class uses a fixed array whose size is determined when a class object is instantiated. Change this to use a dynamic array as implemented using a vector. Several changes will be needed throughout the code. You will need to add values to the end of the vector using push_back and you will need to remove values from the end of the vector using pop_back. Otherwise, the vector will not be able to keep track of the number of elements and do dynamic allocation properly. Eliminate any member variables and functions you no longer need. Compile and test the code.

3. The code requires a function called Min_Val to be created by the user program. This makes the code marginally more efficient, but error prone and less flexible. Change the program to eliminate the need for this function. Be certain that your program puts a dummy value into the 0th location of the vector or changes the program to store values in locations 0 through n-1.

4. Write a Binary_Heap constructor that converts an array to a heap (stored as a vector, of course). Here is pseudo-code to rearrange an array (or a vector) as a heap.

        for ( i=N/2; i>=1; i--)  Percolate_Down(i);
   

   (This is based on storing the values in locations 1 through N of the array (vector) - storing the values in locations 0 through N-1 requires a trivial change.) It will run in linear time, as will be discussed in class. The code for "percolate down" is currrently implemented in Build_Heap::Delete_Min. Rewrite the code to make Percolate_Down a separate (private) member function.

5. Write a function that uses the Binary_Heap class to sort an array. Demonstrate that it works.

At the conclusion of this lab, take a moment to review the following:

You should note the improvements to the Binary_Heap class that make it more flexible and easier to use.

You have begun to see how a binary heap can be used for sorting. It is a relatively simple matter to show that the time required for this sort is O(n log n).