Homework 5 - A priority queue implemented as a heap

Homework 5
Implement and Test a Class for a Priority Queue, using a Heap

Due: December 14, 2004 at 11:59pm

Assignment

Implement the priority_queue class, using a heap to store the items, as described in Section 11.1. Your priority_queue class will use a heap that is stored in a fixed-size array. The component type of the array is a struct called one_item_info, and is defined as part of the priority_queue class in pqueue2.h. (Note that in C++ a struct is like a class, except that by default every data member in a struct is public.) Do not make any changes to pqueue2.h for this assignment. In addition to the public member functions insert() and get_front(), you must write and use all the private helper functions that are listed in pqueue2.h (in other words, make sure each private helper function is called at least once from a member function) . The precondition/postcondition contracts for these helper functions are given in pqueue2.cxx.

Outcomes

After successfully completing this assignment, you will be able to...

implement a priority queue using a heap
write C++ code that uses structs

Before Starting

Read Chapters 10.1 and 11.1.

What you should do

You should follow the same general procedure as you used for HW2, HW3, and HW4:

Create a directory to hold your hw5 files, and cd to that directory.
Copy the files from the class directory to your hw5 directory:
cp /cs/cs2005/hw/hw5/* .
Your hw5 directory should now contain these files: pqueue2.h, pqueue2.cxx, pqtest.cxx.
Create a makefile to do the compiling and linking for you. Here are the names of the files you will be using in this project: pqueue2.h (you'll be using this file unchanged), pqueue2.cxx (you'll be modifying this file in step 4, below), pqtest.cxx (you will use this client file as it is, unchanged).
Modify the implementation file pqueue2.cxx so that it contains stubs for all of the priority_queue member functions. Do not attempt to fully implement any of the member functions yet, just write them as stubs. Using your makefile, compile and build your program. Do not proceed beyond this point until you get a program that compiles and builds with no errors.
Replace each stub in pqueue2.cxx with functional code. I suggest you implement the functions in this order:
- constructor.
- the functions needed to implement the insert() public member function. You will have to write the code for the private member functions parent_index(), parent_priority(), and swap_with_parent(), as well as the code for insert(). Compile your files and run the test program, pqtest. Thoroughly debug this portion of the program before you attempt the next step.
- the functions needed to implement the get_front() public member function. You will have to write the code for the private member functions big_child_index(), big_child_priority(), and is_leaf(), as well as the code for get_front(). Compile, run, and test.
When you have implemented all the member functions, and have thoroughly tested your program, submit your header and implementation files for the priority_queue class, and your makefile, using the following turnin command:
/cs/bin/turnin submit cs2005 hw5 pqueue2.h pqueue2.cxx makefile

Grading

(90 points) Points will be awarded for

implementing each member function so that it meets specifications consistent with a heap implementation of the priority_queue class
using each private member function
correctness of the makefile

Programs must build successfully in order to receive credit. (If your program does not build, the grade on the homework will be zero.)