CS 14 - Lab 8

Array Implementation of a Binary Heap (and experience with pointers)

In this lab you will be implementing a max heap (the highest number will be the root). You will be simulating a print queue and each print job will be represented as a class called PrintJob. You must implement the enqueue, dequeue, print, and highest functions for your heap class and various functions for the PrintJobs class. Your heap will be implemented as a dynamically allocated array of print job pointers (this will perhaps give you an experience with pointers that you have not yet had).

Provided files

heap.h - The class for your heap. Notice that the heap is represented as a dynamically allocated array of pointers. You must implement AT LEAST the following functions to interface with main.cc. (NOTE: these may not be the only heap functions you will need to write for the heap to function correctly).
- void enqueue ( PrintJob* ) - Enqueue the PrintJob into the heap
- void dequeue ( ) - Dequeue the highest priority job
- PrintJob highest ( ) - Return a pointer to the highest priority job. Returns null if the heap is empty
- void print ( ) - Prints all of the jobs in the heap in the order that they appear in the array. Overload the insertion operator to print each print job. You must adhere to the following print specifications. Each print job will be printed like this (just what is in the quotes, do not print the quotes): "(priority, numPages, jobNumber)". All print jobs are printed on a single line with no spaces between them and a return at the end of the line. Here is an example of three print jobs: (3, 4, 5)(1, 2, 3)(2, 3, 4)
printjob.h - The class for your print jobs. It has three variables: priority (the priority of the print job), numPages (the number of pages to print), and jobNumber (the job number assigned to the print job). You must implement AT LEAST the following functions to interface with main.cc. (NOTE: these may not be the only PrintJob functions you will need to write for the heap to function correctly).
- int getPriority ( ) - return the priority of the print job
- int getPages ( ) - return the number of pages for the print job
- int getJobNumber ( ) - return the job number of the print job
- Furthermore, you must overload the insertion operator to print the printjob to the screen (more details are above on printing) and the > operator so you can compare the priorities of the printjobs.
main.cc - the main test file that you will be using to test your program

Point Breakdown For Lab Assignment

You will demo your binary heap in lab. The TA will look at the output of main.cc to verify that your heap works. (You will need to download a fresh copy of main.cc while the TA is watching) The TA will then verify that you did indeed write the code to do this. Remember, to receive credit for this lab, you MUST turn the code in online. If you do not turn in your code online, you will lose points for your lab. All code must be turned in online for archival purposes.

2 points - Attendance is, as always, worth 20% of your lab grade.
1 point - Passes test 1
1 point - Passes test 2
1 point - Passes test 3
1 point - Passes test 4
2.1 points - Passes test 5 (.3 for each dequeue operation passed)
.9 points - Print looks exactly as I specified
1 point - Overloaded the > and insertion operator for the print job class
Deductions -

-1 point - if your program seg faults at any point during execution.
-1 point - not using a makefile
-1 point - program does not compile with the standard flags: -Wall -Werror -W -pedantic
-4 points - Changing the array in the heap to anything else (you must use the PrintJob** arr as it is declared in the heap class).
-10 points - Not implementing a binary heap but rather simulating a binary heap using a different data structure
-1 point - not logically seperating your code into seperate files
-5 points - Turned into the wrong lab section.
-1 point - No name on work turned in
-5 points - Code not turned in at all. This deduction also applies to turnins that do not contain a the partners name (only the name that is not on the turnin will have 5 points deducted. The person that actually turned the code in will only have 1 point deducted if their name is not on the turnin).
-5 points - If your currently assigned partner is in lab and you do not work together.