Program 8 - Heaps

COSC 2415 Data Structures
Bob Comer, Professor of Computer Studies

Program 8 - Heaps

Be sure to read through Chapter 13 section 13.3 of the textbook before starting this assignment.

Write a function that will take an integer array and turn it into a heap (the heapify algorithm in your textbook). Your function should have 2 parameters - the integer array and the size (the number of elements in the array to be sorted).

For 10% extra credit, write a second function to perform a heapsort on an integer array. Again, this function should have 2 parameters - the integer array and the size (the number of items in the array to be sorted).

Note 1: You do not have to create a Heap class.

Note 2: The C++ Standard Template Library contains functions for creating and manipulating heaps. I WILL NOT accept an assignment that uses the STL. You must write your own heap functions.

Note 3: Some of the sort algorithms in Chapter 13 of the textbook use index 0 of the array for special purposes. So all the sort algorithms in the textbook assume that the data to be sorted are stored at indexes 1 through size (instead of the normal 0 through size - 1). So if you follow the algorithms in the book, the size of your array needs to be number of items to sort + 1.

Note 4: There is an error in the percolate_down algorithm in my copy of the textbook. Be sure to check if this error is in your book. The percolate_down algorithm is on page 739 of your textbook. See:

Errata

My book has:

2. While r <= n do the following:

The correct instruction is:

2. While c <= n do the following:

Note 5: There is also a quirk in the heapify algorithm. When it calls the percolate_down algorithm, r should be passed by value. In other words, the percolate_down algorithm modifies r, but this should not change the r in the heapify algorithm.

Be sure to document your functions with a precondition and a postcondition. These should clearly state whether the items to be sorted are in indexes 1 through size, or 0 through size - 1.

To test your heapify function (or heap sort function), write a driver program to do the following:

Repeat until user is ready to quit
   Input the size (number of items to be sorted) from the user
   Dynamically allocate an array to hold the items to be sorted
   Input size integers from the user and store them in your array
   Call your function to heapify (or heap sort) the array
   Display the results
   Free the array
End repeat

Return to Data Structures Home Page