Heap Implementation
In class, we covered the algorithms for an array-based heap implementation, paying attention only to the keys in the heap. To use a heap to implement a priority queue, you also need to keep track of elements associated with each key. (We want extract_min to give us the element with the highest priority. We may or may not care what the priority value is.) For this assignment, you are to implement a C++ heap class, which stores pairs , where each element and priority value is an int.
Begin by getting the files heap.h (provided), Makefile (provided) and test1.cpp (provided). The implementation is incomplete, and your task is to complete it. Both the class declaration and the function implementations are in the .h file (as if we were making a template class, but this assignment does not involve a template class.)
Advice
Start by carefully examining the header file, and studying the given partial implementation. Extend the current implementation by one function at a time, always making sure all completed functions work correctly (and that previously completed functions did not stop working as a result of the changes) before proceeding to the next. Extend the test program as you go to accomplish this. (By the end, you should have a test program that thoroughly tests all capabilities of the class.)
Grading
This assignment will be graded out of 8. Roughly speaking, you can think of the grading scheme like this:
It is not feasible to grade exactly according to that scheme, because it is not practical to test the functions completely independently. In practice, we will base your grade on the ouput of a suite of test programs. These programs will be very similar to the following three test programs:
You may conclude that, to get full marks, your class should at least satisfy these properties:
There are no specific marks assigned for style, but marks may be deducted if you submit unreadable code, if you make any dissallowed changes to the declarations, or violate any other explicit requirement.