CMPT 225 Lab 7: Heaps


Implement and test a heap of strings.  Your heap should implement a priority queue (where the highest priority item is always removed first).  Your heap should be a min heap, so the root should always contain the string that comes first in the alphabet.

Start by downloading the zipfile. It contains:


Notes

Implementation

You should implement your heap as discussed in lecture. The remove method (and bubbleDown) has been provided. Please write the insert method. Write a separate private bubbleUp method that should be called by your insert method.

Comparing Strings

We are using the C++ strings defined in <string>, std::string (using namespace std you can omit the std::). If you want to compare two strings you can use the operators >, <, ==, since these are properly overloaded for the string class.


Testing

Test your Heap class by running the python script test.py.

uname@hostname: ~$ ./test.py

Please run this for a TA successfully (3 tests passed) to receive your 1 mark for this lab.


Debugging

Please modify the driver heap_debug.cpp if you wish to add debugging calls. Final versions of Heap methods should not produce any output to cout, since cout's output is used for correctness checks by test.py. If your code fails a test case, you can try running it individually, and comparing it to the corresponding ground truth file. E.g. to run test case 1 and examine its ground truth:

uname@hostname: ~$ ./heap_test < 1.in
uname@hostname: ~$ more 1.gt



Back to the CMPT 225 homepage.