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.


Last Revised: 2016-09-14
© Copyright 2016 by Peter C. Chapin <PChapin@vtc.vsc.edu>