---

Outline:

• Description
• Implementation
• Style
• FAQ
• Extras

This problem focuses on implementing a heap, although you have a choice on the type of heap that you implement.

The problem demonstrates the modularity and nature of Abstract Data Types: you are responsible for replacing all public functionality of the PatientQueue class from part A with a heap structure. In other words, the patientqueueheap.h header file will have exactly the same public declaration as patientqueue.h from part A, but patientqueueheap.cpp will be implemented with a Heap instead of a Linked List. The private section of your patientqueueHeap.h file should be modified to comply with your heap class variables, functions, etc. In other words, you are making a drop-in replacement for the PatientQueue class, which should be faster than the Linked List implementation. This is an individual assignment. Write your own solution and do not work in a pair/group on this program.

Files and Links:

Problem Description:

This problem is identical to the Patient Queue from part A of this assignment.

Implementation Details:

You may choose to implement any of the following heaps to create your PatientQueueHeap.

We will go over the binary heap in lecture, but if you decide to implement a different type of heap, you will be responsible for researching how the data structure works.

Note: In your investigation, you may find that others have implemented the particular heap you have chosen in code (C++ or another language). You are not permitted to look at the code to implement your solution -- you must use descriptions and pseudo-code only. There is a somewhat fine line between using actual code and pseudocode, but you can consider pseudo-code to be a description of the algorithm. If you have any concerns, please reach out to either Chris, Aaron, or your Section Leader for clarification.

The heaps you may choose from are roughly ranked from easy to hard below:

• Binary Heap (as described in lecture): https://en.wikipedia.org/wiki/Binary_heap.
• Binomial Heap: https://en.wikipedia.org/wiki/Binomial_heap
• 2-3 Heap: https://en.wikipedia.org/wiki/2–3_heap
• Fibonacci Heap: https://en.wikipedia.org/wiki/Fibonacci_heap
• Leftist Tree: https://en.wikipedia.org/wiki/Leftist_tree
• Other: see below

There are many other types of heaps you could build. If you would like to choose a different type of heap, you must schedule an appointment with Chris to discuss it -- we will look at the data structure and see if it is appropriate for the assignment.

PatientQueue Operations:

As with Part A, your class must support all of the following operations. Note that the Big O column is not filled in: part of the assignment involves annotating all of your functions (in a function comment) with the Big O for each function.

Member Name	Description	Big-Oh
PatientQueue()	In this parameterless constructor you should initialize a new empty queue.
~PatientQueue()	In this destructor you must free up any memory used by your heap.
pq.newPatient(name, priority);	In this function you should add the given person into your patient queue with the given priority. Duplicate names and priorities are allowed. Any string is a legal value, and any integer is a legal priority; there are no invalid values that can be passed.
pq.processPatient()	In this function you should remove the patient with the most urgent priority from your queue, and you should also return their name as a string. You should throw a string exception if the queue does not contain any patients.
pq.frontName()	In this function you should return the name of the most urgent patient (the person in the front of your patient queue), without removing it or altering the state of the queue. You should throw a string exception if the queue does not contain any patients.
pq.frontPriority()	In this function you should return the integer priority of the most urgent patient (the person in the front of your patient queue), without removing it or altering the state of the queue. You should throw a string exception if the queue does not contain any patients.
pq.upgradePatient(name, newPriority);	In this function you will modify the priority of a given existing patient in the queue. The intent is to change the patient's priority to be more urgent (a smaller integer) than its current value, perhaps because the patient's condition has gotten worse. If the given patient is present in the queue and already has a more urgent priority than the given new priority, or if the given patient is not already in the queue, your function should throw a string exception. If the given patient name occurs multiple times in the queue, you should alter the priority of the first occurrence of the value in your heap.
pq.isEmpty()	In this function you should return true if your patient queue does not contain any elements and false if it does contain at least one patient.
pq.clear();	In this function you should remove all elements from the patient queue, freeing memory for your heap structure.
ostream << pq	You should write a << operator for printing your patient queue to the console. The elements should be printed out in front-to-back order and must be in the form of value:priority with {} braces and separated by a comma and space, such as: {2:Ford, 4:Bernard, 5:Dolores, 5:William, 5:Teddy, 8:Arnold} The PatientNode structure has a << operator that may be useful to you. Your formatting and spacing should match exactly. Do not place a \n or endl at the end of your output.

The headers of every member must match those specified above. Do not change the parameters or function names.

Constructor/destructor: Your class must define a parameterless constructor. Since your implementation allocates dynamic memory (using new), you must ensure that there are no memory leaks by freeing any such allocated memory at the appropriate time. This will mean that you will need a destructor to free the memory for your heap.

Helper functions: The members listed on the previous page represent your class's required behavior. But you may add other member functions to help you implement all of the appropriate behavior. Any other member functions you provide must be private. Remember that each member function of your class should have a clear, coherent purpose. You should provide private helper members for common repeated operations.

You will also need to do the following:

Add descriptive comments to PatientQueue.h/cpp. One comment for each file should be the Big O for that function. Both files should have top-of-file headers; one file should have header comments atop each member function, either the .h or .cpp; and the .cpp should have internal comments describing the details of each function's implementation.

Declare your necessary private member variables in PatientQueue.h, along with any private member functions you want to help you implement the required public behavior. Your inner data storage must be a heap; do not use any other collections or data structures in any part of your code.

Implement the bodies of all member functions and constructors in PatientQueue.cpp.

Here are a few other constraints we expect you to follow in your implementation:

You should not make unnecessary passes over the heap.

Duplicate patient names and priorities are allowed in your queue. For example, the upgradePatient operation should affect only a single occurrence of a patient's name (the first one found). If there are other occurrences of that same value in the queue, a single call to upgradePatient shouldn't affect them all.

You are not allowed to use a sort function or library to arrange the elements of your heap, nor are you allowed to create any temporary or auxiliary data structures anywhere in your code. You must implement all behavior using only the heap.

You will need pointers for several of your implementations, but you should not use pointers-to-pointers (for example, PatientNode**). If you like, you are allowed to use a reference to a pointer (e.g. PQNode*&).

Style Details:

As in other assignments, you should follow our Style Guide for information about expected coding style. You are also expected to follow all of the general style constraints emphasized in the Homework 1-4 specs, such as the ones about good problem decomposition, parameters, redundancy, using proper C++ idioms, and commenting. The following are additional points of emphasis and style contraints specific to this problem. (Some of these may seem overly strict or arbitrary, but we need to constrain the assignment to force you to properly practice pointers and heaps as intended.)

Commenting: Add descriptive comments to your .h and .cpp files. Both files should have top-of-file headers. One file should have header comments atop each member function (either the .h or .cpp; your choice). The .cpp file should have internal comments describing the details of each function's implementation.

Restrictions on pointers: The whole point of this assignment is to practice implementing a heap. Therefore, do not declare or use any other collections in any part of your code; all data should be stored in your heap. There are some C++ "smart pointer" libraries that manage pointers and memory automatically, allocating and freeing memory as needed; you should not use any such libraries on this assignment.

Restrictions on modifying member function headers: Please do not make modifications to the PatientQueue class's public constructor or public member functions' names, parameter types, or return types. Our client code should be able to call public member functions on your queue successfully without any modification.

Avoiding memory leaks: This item is listed under Style even though it is technically a functional requirement, because memory leakage is not usually visible while a program is running. To ensure that your class does not leak memory, you must delete the entire heap in your destructor.

Frequently Asked Questions (FAQ):

For each assignment problem, we receive various frequent student questions. The answers to some of those questions can be found by clicking the link below.

Possible Extra Features:

For this problem, you are welcome to implement any of the extensions from Part A of the assignment, or you are welcome to implement a different type of heap.

Indicating that you have done extra features: If you complete any extra features, then in the comment heading on the top of your program, please list all extra features that you worked on and where in the code they can be found (what functions, lines, etc. so that the grader can look at their code easily).

Submitting a program with extra features: Since we use automated testing for part of our grading process, it is important that you submit a program that conforms to the preceding spec, even if you want to do extra features. If your feature(s) cause your program to change the output that it produces in such a way that it no longer matches the expected sample output test cases provided, you should submit two versions of your program file: a first one with the standard file name without any extra features added (or with all necessary features disabled or commented out), and a second one whose file name has the suffix -extra.cpp with the extra features enabled. Please distinguish them in by explaining which is which in the comment header. Our turnin system saves every submission you make, so if you make multiple submissions we will be able to view all of them; your previously submitted files will not be lost or overwritten.