Description
The Assignment:
Implement the Priority Queue class, using a heap to store the items, as described in Section 11.1.
Purposes:
Ensure that you understand and can use heap which is implemented in an array.
Before Starting:
Read all of Sections 8.4, 10.2 and 11.1 (primary)
Files that you must write:
-
pqueue2.h: Header file for this version of the PriorityQueue class. You don’t have to write much of this file. Just copy our version from http://geoteci.engr.ccny.cuny.edu/CSc212/pqueue2.h and add your name and other information at the top.
-
pqueue2.cxx: The implementation file for the new PriorityQueue class. A version that contains just stubs is available for you to copy http://geoteci.engr.ccny.cuny.edu/CSc212/pqueue2.cxx
Other files that you may find helpful:
-
pqtest.cxx: A simple interactive test program for debugging your program. http://geoteci.engr.ccny.cuny.edu/CSc212/pqtest.cxx
-
pqexam2.cxx: A non-interactive test program that will be used to grade the correctness of your Priority Queue class. http://geoteci.engr.ccny.cuny.edu/CSc212/pqexam2.cxx
Discussion of the Assignment
Your PriorityQueue class for this assignment will use a heap that is stored in an array. The component type of the array is called OneItemInfo, and is defined as part of the PriorityQueue class in pqueue2.h. In order for you to further learn how to use private member functions, I would like for you to write and use all the private member functions that are listed in pqueue2.h. The precondition/postcondition contracts for these functions are given in the stub version of pqueue2.cxx.
Do the Assignment in Two Parts
For easier debugging, carry out this assignment in two Parts. Part 1 should include everything except the public get_front member function and the private functions that are needed for get_front (i.e., is_leaf, big_child_index, and big_child_priority). While you are debugging Part 1, you should add a new option to the interactive test program. The new option makes this call to print the current state of the tree of the test PriorityQueue: test.print_tree(“STATE OF THE TREE:”). (Note that print_tree is a public member function that I wrote for you. You should remove it before you submit your final work.)
Once Part One is working and tested, you may complete the assignment by implementing the get_front member function and its associated private functions.
Use the interactive test program and the debugger to track down errors in your implementation. If you have an error, do not start making changes until you have identified the cause of the error.
