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:
https://www.cs.rpi.edu/academics/courses/spring17/ds/labs/13_priority_queues/priority_queue.h https://www.cs.rpi.edu/academics/courses/spring17/ds/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 0
Turn in a hardcopy of the class inheritance hierarchy for Homework 10. Neatness & correctness are important! Make a copy (e.g., take a photo) of your diagram so you can refer to it while you finish the implementation.
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.
Checkpoint 3
Finally, write and test the non-member function that sorts a vector by constructing a binary heap. This code should sort the data “in place” and not require a large scratch space (e.g., another vector or list) to store a copy of the data as it is being sorted.
For the remainder of lab time, work on Homework 10 and ask your graduate TA & undergraduate mentors plenty of questions.
To complete this checkpoint and the entire lab: Show a TA your completed and debugged heap sort code and present your progress on Homework 10.