Description
In this lab, you will use binary heaps to implement the priority queue container, as discussed in Lectures 21 & 22. Having these notes available while you are working on this lab will make it substantially
easier. Start by downloading the files, and then turn off all network connections:
http://www.cs.rpi.edu/academics/courses/fall14/csci1200/labs/13_priority_queues/priority_queue.h
http://www.cs.rpi.edu/academics/courses/fall14/csci1200/labs/13_priority_queues/test_pq.cpp
The code provided in these files is straightforward. test_pq.cpp is a driver and test program, while
priority_queue.h is a skeleton implementation. Please take a careful look. You will complete the implementation and add to the main program in lab. In your implementation, be careful when subtracting 1
from an unsigned int whose value is 0; it is not -1!
Checkpoint 1
Implement and test the push (a.k.a. insert) and the check_heap functions. Recall that push depends on
the percolate_up functionality. check_heap, which works either with the heap member variable or with a
vector provided from the outside, determines if the vector is properly a heap, meaning that each value is less
than or equal to the values of both of its children (if they exist).
To complete this checkpoint: Show a TA your debugged implementation and discuss the running time
of both insert and check_heap.
Checkpoint 2
Implement and test the pop (a.k.a. delete_min) function and the constructor that builds a valid heap from
a vector of values that is in no particular order. Both of these depend on proper implementation of the
percolate_down function.
To complete this checkpoint: Show a TA these additions and the test output.
