CMPT 225 Assignment 3: 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, Makefile and test1.cpp. 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.)

Do not make any changes to the given function declarations.
Complete the implementations of all incompletely implemented functions.
You may add private functions if you find it useful.
The small test program test.cpp is provided for convenience only. You should extend it with further testing.
You may extend the provided makefile if it is useful, but make sure that the provided one still works, because we will use it (or something similar) for testing your 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:

1 mark for correctness of each of the functions (including constructors) which you need to implement.
1 mark each for giving recursive implementations of trickleDown and trickleUp.

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:

The three test programs must compile and run, using your heap class, on the CSIL Linux worstations, using this Makefile.
The programs test2 and test4 must output a total of 5 ones.
Your implementations of trickleUP and trickleDown must be recursive.

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.

Submission

You should submit a zip file containing your heap.h file (and nothing else) online to the CourSys submission server. The assignment is due by 7:00pm on Tuesday November 22.