CIS-3050 Homework #4: Heaps

Due: Wednesday, September 21, 2016

1. Modify Sorters.h to include the following declarations:

   // Forces sequence starting at first to be a valid heap in O(n) time.
   void make_heap( void *first, size_t element_count, size_t element_size, int( *compare )( void *, void * ) );
   
   // Inserts the item at the end of the heap in O(log(n)) time.
   void push_heap( void *first, size_t element_count, size_t element_size, int( *compare )( void *, void * ) );
   
   // Moves maximum item in the heap to the last item in O(log(n)) time
   void pop_heap( void *first, size_t element_count, size_t element_size, int( *compare )( void *, void * ) );
   
   // Sorts the (already valid) heap in O(n log(n)) time.
   void sort_heap( void *first, size_t element_count, size_t element_size, int( *compare )( void *, void * ) );
         

   In class I provided the implementation of make_heap, push_heap, and pop_heap. These implementations, along with place holders for the functions you must write are in the file Homework-04.cpp. Note that my implementations rely on an internal function heapify.

2. Implement function heapify following the Heapify pseudo-code developed in class.

3. Implement function sort_heap using heapify.

4. In the UnitTests project modify the file SortersTests.cpp to add new tests for HeapSort. You can copy the MergeSort tests and make a few adjustments.

Submit your file Homework-04.cpp to Moodle. Alternatively you could put all the code into your Sorters.cpp and upload that file instead.