In class we have learned about queues that process elements in a first-in, first-out (FIFO) order. But FIFO is not the best order for all problems — for example, for a problem like assisting patients in a hospital, some patients have more critical injuries than others. In this problem, you will write several implementations of a collection class modeled on this type of queue—also known as a priority queue — for a hospital waiting room.

For the PatientQueue classes that you will write, you can imagine that as each new patient checks into the hospital, the staff assesses the patient’s injuries and gives them an integer priority rating. Smaller integers represent greater urgency; for example, a patient of priority 1 is more urgent and should receive care before a patient of priority 2. Once a doctor is ready to see a patient, the patient with the most urgent priority (i.e., with the lowest number rating) is seen first.

Due Date: Thurs., May 17 at 6:00pm PST.
YEAH Hours: Fri., May 11 3:30-4:20pm in Skilling Auditorium. Video and slides linked later in the spec.

Your assignment has three parts: first, you will implement a PatientQueue class using a Stanford Libraries Vector. Then, you’ll implement a PatientQueue class using a linked list that you design. Finally, you'll implement a PatientQueue class using something called a heap (which is how most real-world Priority Queues are implemented). Though the implementation details will differ, these classes should have identical behavior from the user’s perspective. This assignment is designed to give you more practice with creating your own classes and handling pointers. Later implementations are more difficult than the earlier ones. Start early, proceed slowly, and draw lots of pictures. If you do so, we think you’ll find that this assignment is not as complex as it originally seems!

Starter Code

Turn in only the following files via the Paperless submitter:

  1. VectorPatientQueue.h/.cpp
  2. LinkedListPatientQueue.h/.cpp
  3. HeapPatientQueue.h/.cpp

Pair Programming

You may optionally work on this assignment as a pair programming assignment. If you would like to work in a pair on this assignment, you may, under the following conditions:

  • Both partners must be in the same section (time and location).
  • At no time should partners be coding alone. To be clear: all coding must be done together, on a single computer. One partner should type, and the other should watch over that partner's shoulder. Each partner should take turns at the keyboard.
  • When you go to the LaIR or office hours for help on your assignment, both students must be present in the pair to receive help. Only one partner should sign up for help in the LaIR Queue at a time.
  • Pair programming is less about sharing the workload and more about sharing ideas and working together. During the IG for the assignment, if a Section Leader does not think both partners contributed equally and worked together, the SL may forbid pair programming on a future assignment.
  • Pairs who "split the assignment" where one partner does part of the assignment alone, and the other partner does another part of the assignment alone, will be in violation of the Honor Code.

YEAH Hours

The recording from the YEAH hours session can be found on Canvas. The slides can be found here.

Sample Output


A priority queue can be understood as storing a set of keys (priorities) and their associated values (in our case, patient names). The basic design of the priority queue is that, regardless of the order in which you add/enqueue the elements, when you remove/dequeue them, the one with the lowest number comes out first, then the second-lowest, and so on, with the highest-numbered (i.e., least urgent) item coming out last.

In your implementations of the PatientQueue, if two or more patients in the queue have the same priority, you should break ties by choosing the patient who arrived earliest. This means that if a patient arrives at priority K and there are already other patients in the queue with priority K, your new patient should be placed after them.

For example, suppose the following patients arrive at the hospital in this order:

  1. "Dolores" with priority 5
  2. "Bernard" with priority 4
  3. "Arnold" with priority 8
  4. "William" with priority 5
  5. "Teddy" with priority 5
  6. "Ford" with priority 2

If you were to dequeue the patients to process them, they would come out in this order: Ford, Bernard, Dolores, William, Teddy, Arnold. (Note that tie breaking works differently in the binary heap implementation; see details in that section.)

A priority queue can internally store its elements in sorted or unsorted order; all that matters is that when the elements are dequeued, they come out in sorted order by priority. The parts of this assignment will require you to experiment with both kinds of storage: your Vector must be unsorted, and your linked list and heap must be sorted. The difference between the external expected behavior of the priority queue and its true internal state can lead to interesting differences in implementation, as you will learn while completing this assignment.


For each of your implementations of the PatientQueue, you must write all of the following member functions with the listed runtimes; the N in this context means the length of the list. The headers of every member function must match those specified here. Please do not make modifications to the PatientQueue class’s public constructor or public member functions' names, parameter types, or return types. Doing so will result in a deduction. Our client code should be able to call public member functions on your queue successfully without any modification.

Member Name Description Vector Big-Oh LinkedList Big-Oh Binary Heap Big-Oh
PatientQueue() In this parameterless constructor you should initialize a new empty queue (e.g. with a null front for your internal linked list, and an empty Vector for your Vector class). O(1) O(1) O(1)
~PatientQueue() In this destructor you must free up any memory used— for example, you will need to free your linked list nodes (note that you may not need to do anything in your destructor for your Vector class). O(1) O(N) O(1)
pq.newPatient(name, priority); In this function you should add/enqueue 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. O(1) O(N) O(logN)
pq.processPatient() In this function you should remove/dequeue 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. The string should be a helpful, grammatically correct and concise message that informs the user what went wrong. O(N) O(1) O(logN)
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 (i.e., peek name). You should throw a string exception if the queue does not contain any patients. O(N) O(1) O(1)
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 (i.e., peek priority). You should throw a string exception if the queue does not contain any patients. O(N) O(1) O(1)
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 (i.e., 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 most urgent priority person with that name that was placed into the queue. O(N) O(N) O(N)
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. O(1) O(1) O(1)
pq.clear(); In this function you should remove all elements from the patient queue, freeing memory for all nodes that are removed. O(1) O(N) O(1)
toString() You should write a toString() function for printing your patient queue to the console. The function should return a string in the following format: The elements should be printed out in front-to-back order and must be in the form of priority:value 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 - look into this link for how to use a stringstream to make a string using <<. Your formatting and spacing should match exactly. Do not place a \n or endl at the end of your output. Note: you only have to format the string in priority order for the linked list; it can be in any order for your Vector and heap implementations. O(N) O(N) O(N)

Constructor/destructor: As the table above indicates, your class must define a constructor with no parameters. Since, as we shall see, your linked list implementation must allocate dynamic memory (using new), you must ensure that there are no memory leaks by freeing any such allocated memory at the appropriate time. This means that you will need a destructor to free the memory for all of your nodes.

Helper functions: The members listed above 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. Make a parameter const if it does not perform modification of the parameter's state.

Private member variables: Declare your necessary private member variable in the relevant header file, along with any private member functions you want to help you implement the required public behavior.

Vector Implementation

For part one of this assignment, you will write a VectorPatientQueue class that will use an unsorted Stanford Vector to hold the queue of patients. Because the Vector is unsorted, when de-queueing/processing a patient, you will need to traverse the Vector to find the element with the most urgent priority. This process is inherently inefficient, but don’t worry—that’s why you’ll try out the implementation with sorted linked list storage next.

Inside the VectorPatientQueue.h file, you will find the interface for the VectorPatientQueue class. Your task is to implement the methods exported in this header file. To do so, you will need to define the private fields inside the class and to implement the class’s methods in the VectorPatientQueue.cpp source file.

You should create a struct inside the VectorPatientQueue.h file that holds a patient name and a priority. We strongly suggest that you also define an integer “timestamp” parameter. This will let you distinguish between patients with the same priority who come in at different times—in an unsorted list, you must determine who came in first, and a timestamp is a good way to do that. This timestamp can be based on an incrementing counter elsewhere in your class; every time a patient is enqueued or a patient's priority is updated (since this is the same as re-enqueuing them with a new priority), you update the timestamp and add it to the patient’s struct.

Note that the operations like upgradePatient, newPatient, and processPatient should not needlessly rearrange the elements of the vector any more than necessary. For example, when changing a patient's priority, don't remove and re-add that element to the array.

Try not to overthink the Vector patient queue— its main goal is to help you get used to the idea of a priority queue, and its implementation should be relatively straightforward.

Linked List Implementation

For the second part of this assignment, you will write a LinkedListPatientQueue class that will use a sorted singly linked list as its internal data storage. Your inner data storage must be a singly linked list of patient nodes; do not use any other collections or data structures in any part of your code. As new elements are enqueued, you should add them at the appropriate place in the linked list so as to maintain the sorted order. You should implement the bodies of all member functions and constructors in LinkedListPatientQueue.cpp.

The primary benefit of this implementation is that when removing a patient to process them, you do not need to search the linked list to find the most urgent element and remove/return it; it is always at the front of the list. Enqueuing is slower, because you must search for the proper place to enqueue new elements, but dequeueing/peeking is very fast, and overall performance is fairly good.

For this implementation, we supply you with a PatientNode structure (in patientnode.h/cpp), a small struct representing a single node of the linked list. Each PatientNode contains a string value, an integer priority, and a pointer to a next node. Note that while in the Vector implementation you needed a timestamp to keep track of when patients arrive, for the linked list implementation, you won’t need a timestamp, because the list will be sorted, and patients with the same priority will be sorted in the order in which they arrived.

The following is the PatientNode struct:

struct PatientNode {
    string name;
    int priority;
    PatientNode* next;

    // constructor - each parameter is optional
    PatientNode(string name, int priority, PatientNode* next);

To understand the internal state of the LinkedListPatientQueue, let’s return to the example used above. Suppose again that the following patients arrive at the hospital in this order:

  1. "Dolores" with priority 5
  2. "Bernard" with priority 4
  3. "Arnold" with priority 8
  4. "William" with priority 5
  5. "Teddy" with priority 5
  6. "Ford" with priority 2

The following is a diagram of the internal state of a LinkedListPatientQueue after enqueuing these elements:

front -> {2:Ford} -> {4:Bernard} -> {5:Dolores} -> {5:William} -> {5:Teddy} -> {8:Arnold}

The tricky part of this implementation is inserting a new node in the proper place when a new patient arrives. You must look for the proper insertion point by finding the last element whose priority is at least as large as the new value to insert. Remember that, as shown in class, you must often stop one node early so that you can adjust the next pointer of the preceding node. For example, if you were going to insert the value "Stubbs" with priority 5 into the list shown above, your code should iterate until you have a pointer to the node for "Teddy", as shown below:

front -> {2:Ford} -> {4:Bernard} -> {5:Dolores} -> {5:William} -> {5:Teddy} -> {8:Arnold}
                                                        current ---+

Once the current pointer shown above points to the right location, you can insert the new node as shown below:

front->{2:Ford} -> {4:Bernard} -> {5:Dolores} -> {5:William} -> {5:Teddy}       {8:Arnold}
                                                                 ^      |        ^
                                                                 |      v        |
                                                      current ---+      {5:Stubbs}

Note that the LinkedListPriorityQueue's operations should not make unnecessary passes over the linked list. For example, when enqueuing an element, a poor implementation would traverse the entire list once to count its size and to find the proper index at which to insert, and then make a second traversal to get back to that spot and add the new element. Do not make such multiple passes. Also, do not traverse the list farther than you need to. That is to say, once you have found the node of interest, do not unnecessarily process the rest of the list; break/return out of the traversal as needed once the work is done Also, keep in mind that your queue class is not allowed to store an integer size member variable; you must use the presence of a null next pointer to figure out where the end of the list is/how long it is.

Additionally, don’t create unnecessary PatientNode objects. For example, if a LinkedListPatientQueue contains 6 elements, there should be exactly 6 PatientNode objects in its internal linked list — no more, no less. You shouldn’t, say, have a seventh empty “dummy” node at the front or back of the list that serves just only as a marker, nor should you create a new PatientNode that is just thrown away or discarded without being used as part of the linked list. (This is an unnecessary use of memory.) You can, however, declare as many local variable pointers to PatientNodes as you like. As a hint, the only place in your code where you should be using the new keyword is in the newPatient function. No other members should use new or create new nodes under any circumstances, even by calling other functions. You also should not be modifying or swapping nodes’ name values after they are added to the queue. In other words, you should implement all of the linked list / patient queue operations like upgradePatient by manipulating node pointers, not by creating entirely new nodes and not by modifying the "data" of existing nodes.


Draw pictures: When manipulating linked lists, it is often helpful to draw pictures of the linked list before, during, and after each of the operations you perform on it. Manipulating linked lists can be tricky, but if you have a picture in front of you as you're coding it can make your job substantially easier.

List states: When processing a linked list, you should consider the following states and transitions between them in your code as you add and remove elements. You should also, for each state below, think about the effect of adding a node in the front, middle, and back of the list.

zero nodes
front /
one node
front --> | ? | / |
N nodes
          +---+---+     +---+---+        +---+---+    +---+---+
front --> | ? |   | --> | ? |   |--> ... | ? |   |--> | ? | / |
          +---+---+     +---+---+        +---+---+    +---+---+

Heap Implementation

For the third part of this assignment, you will write a HeapPatientQueue class that will use a binary heap as its internal data storage. Note that you must implement its operations efficiently using the "bubbling" or "percolating" described in this spec. It is important that these operations run in O(log N) time.

As discussed in lecture, a binary heap is an unfilled array that maintains a "heap ordering" property, where each index i is thought of as having two "child" indexes, i * 2 and i * 2 + 1, and where the elements must be arranged such that "parent" indexes always store more urgent priorities than their "children’s" indexes do. To simplify the index math, we will leave index 0 blank and start the data at an overall parent "root" or "start" index of 1. One very desirable property of a binary heap is that the most urgent-priority element (the one that should be returned from a call to peek or dequeue) is always at the start of the data in index 1. For example, the six elements listed on the previous pages could be put into a binary heap as follows. Notice that the most urgent element, "t":2, is stored at the root index of 1.

index     0       1       2       3       4       5       6       7       8       9 
value |       | "t":2 | "m":5 | "b":4 | "x":5 | "q":5 | "a":8 |       |       |       | 
size = 6 
capacity = 10

Adding (enqueuing) a new element into a heap involves placing it into the first empty index (7, in this case) and then "bubbling" or "percolating" up by swapping it with its parent index (i/2), so long as it has a more urgent (lower) priority than its parent. We use integer division, so the parent of index 7 = 7/2 = 3. For example, if we added "y" with priority 3, we would first place it into index 7, then bubble it up by swapping it with "b":4 from index 3, because its priority (3) is more urgent than b's priority (4). This is where the bubbling or swapping would stop, however, because its new parent, "t":2 in index 1, has a more urgent priority than y. So the final heap array contents after adding "y":3 would be:

index     0       1       2       3       4       5       6       7       8       9 
value |       | "t":2 | "m":5 | "y":3 | "x":5 | "q":5 | "a":8 | "b":4 |       |       |
size = 7 
capacity = 10

Removing (dequeuing) the most urgent element from a heap is not a simple matter of removing the “root” or start element at index 1. If we were to simply remove the element at the root index (say, by re-indexing our array), our tree would no longer have the proper structure (look at a picture of a binary heap tree to see why, if this is not yet clear). So instead, after we extract the data from our root element, we move the element from the last occupied index (7, in this case) all the way up to the "root" or "start" index 1, replacing the root that was there before. Then, we "bubble" or "percolate” that element down: as long as it has a less urgent (i.e., higher) priority index than its child, we swap it with that child (located at index i*2 or i*2+1). For example, if we removed "t":2, we would first swap up the element "b":4 from index 7 to index 1, then bubble “b”:4 down one level, by swapping it with its more urgent child, "y":3 because the child's priority of 3 is more urgent than b's priority of 4. It would not swap any further because its new child (which is an only child), "a":8 in index 6, has a less urgent priority than b. So the final heap array contents after removing "t":2 would be:

index     0       1       2       3       4       5       6       7       8       9 
value |       | "y":3 | "m":5 | "b":4 | "x":5 | "q":5 | "a":8 |       |       |       |
size = 6 
capacity = 10

A key benefit of using a binary heap to represent a priority queue is efficiency—this is why most priority queues are now implemented using binary heaps, as we noted above. The common operations of enqueue and dequeue take only O(log N) time to perform, since the "bubbling" jumps by powers of 2 every time. The peek operation runs in just O(1), since the most urgent- priority element is always at index 1.

If nodes ever have a tie in priority, break ties by comparing the strings themselves, treating strings that come earlier in the alphabet as being more urgent (e.g. in lexicographic order, where "a" comes before "b"). Compare strings using the standard relational operators like <,<=,>,>=,==,and!=. Do not make assumptions about the lengths of strings.

Changing the priority of an existing value requires you to loop over the heap to find that value; once you find it, set its new priority and bubble that value up from its present location, somewhat like an enqueue operation.

When the array becomes full and has no more available indices in which to store data, you must resize it to a larger array. Your larger array should be a multiple of the old array size, such as double the size. You must not leak memory; free all dynamically allocated arrays created by your class.

Other Implementation Details

Here are a few other constraints we expect you to follow in your implementations that don't fit neatly into any other section:

  • Duplicate patient names and priorities are allowed. For example, the upgradePatient operation should only affect a single occurrence of a patient's name (specifically, the one with the most urgent priority). If there are other occurrences of that same value in the queue, a single call to upgradePatient shouldn't affect them all.
  • Do not use a sort function or library to arrange the elements of your list.
  • Do not create any temporary or auxiliary data structures anywhere in your code. You must implement all behavior using only the primary internal data structures as specified. For instance, in LinkedListPatientQueue all data should be stored in your linked list of nodes. 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.
  • 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. PatientNode*&).
  • Make sure none of your classes "leak" memory. For example, you must delete all of the node objects in your linked list whenever data is removed or cleared from the list. You must also properly implement a destructor that deletes the memory used by all of the linked list nodes inside your PatientQueue object. Make sure that any data created with the new keyword is properly deleted.

Follow the Honor Code on this assignment. Submit your own (pair's) work; do not look at others' solutions. Cite sources. Do not give out your solution or place it on a public web site or forum. The Stanford C++ library includes a priority queue similar to the HeapPriorityQueue you must implement. We ask that you do not look at that file's source code because it is too similar to what you are asked to do here. You must solve the problem yourself.

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 specs for Homeworks 1-4, such as those regarding good problem decomposition, parameters, redundancy, using proper C++ idioms, and commenting. The following are additional points of emphasis and style constraints specific to this problem.

Commenting: Add descriptive comments to your .h and .cpp files. Both files should have top-of- file header comments that summarize what your program does, and how. 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.

Redundancy: avoid repeated logic as much as possible. Your classes will be graded on whether you make good choices about what members it should have, and other factors such as which are public vs. private, and const-correctness, and so on. You may find that there are some operations that you have to repeat in all of your classes, like checking whether a queue is empty before dequeuing from it. We do not require you to reduce redundancy across multiple classes; but we do expect you to remove redundancy within a single class. If one implementation has a common operation, make a private helper function and call it multiple times in that file.

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

Congratulations—that’s all! You are done. Now consider adding extra features.