CS 14 - Lab 2

In this lab you are going to implement the heapsort algorithm to sort an array of integers by writing functions for HEAPIFY, BUILD-HEAP, and HEAPSORT algorithms given on pages 143-147 of the textbook.

The Functions

The algorithms as written in the book assume that the size of the heap or the length of the array are known. This information must be passed in to your functions, however, so your functions will include an extra parameter. Here are the prototypes for the functions you will write:

   void Heapify( int *Array, int index, int heapSize );
   void BuildHeap( int *Array, int arraySize );
   void Heapsort( int *Array, int arraySize );

Remember that the algorithms as listed in the book assume the array starts with index 1 but in C++ arrays start with index 0. You will need to modify the algorithms to deal with this. For example, line 6 of the HEAPIFY algorithm (page 143) says:

   if r <= heap-size[A] and A[r] > A[largest]

When converting this statement to C++, you would write something like:

   if ( r < heapSize && A[r] > A[largest] )

Notice that the <= was changed to <. Why?

You will also need to create functions for the LEFT and RIGHT algorithms given on page 141 of the book. Notice that the formulas given for these operations do not work properly with 0-indexed arrays. This can easily be rectified, however, by doing the following in each function:

Add 1 to the index passed into the function
Calculate the left or right child index using the formulas in the book
Subtract 1 from the result and return it

The main() Function

Write a main() function to test your heapsort algorithm. The program should prompt the user for the size of an array to be sorted from 1 - 1,000,000. Keep asking the user to enter the size until a number is entered that is within this range.

Once the user has entered the size, your function should dynamically allocate an array of the desired size using the new function (make sure and check that the memory allocation succeeded), populate the array with numbers sorted in descending order, print the contents of the array, call the Heapsort function, then print out the contents of the array again to show that they have been sorted.

Following is a sample run of the completed program:

This program will take an array of numbers in descending order and sort them
into ascending order using the heapsort algorithm.

Please enter an integer from 1 - 1000000: -5
Please enter an integer from 1 - 1000000: 5

The array before sorting: 5 4 3 2 1
The array after  sorting: 1 2 3 4 5

Grading

When you have finished the program, your TA will grade it. To receive full credit, your TA will check all of the following:

The program works correctly
You created each the functions as listed above
The program is properly commented. Each function should have a comment at the beginning explaining what it does, what each of its parameters are for, and the return value (if any). In addition, the code within each function should have comments as appropriate to explain how the algorithms work.
The program is well formatted (i.e. style). For example, you should be consistent with your indenting in the program.