Patients Priority Queue

Assignment

You will write a class called PatientQueue. In this class we have learned about queues that process elements in a first-in, first-out (FIFO) order. But FIFO is not the best order to assist patients in a hospital, because some patients have more urgent and critical injuries than others. As each new patient checks in at the hospital, the staff assesses their injuries and gives that patient an integer priority rating, with smaller integers representing 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 (smallest) priority is seen first. That is, regardless of the order in which you add/enqueue the elements, when you remove/dequeue them, the one with the most urgent priority (smallest integer value) comes out first, then the second-smallest, and so on, with the least urgent priority (largest integer value) item coming out last. A queue that processes its elements in order of increasing priority like this is also called a priority queue.

For a binary minimum heap, the element with the minimum priority value is the frontmost. That is, regardless of the order in which you add/enqueue the elements, the minimum priority element is dequeued first, then the second-smallest, and so on, with the largest priority element coming out last.

For example, if the following patients arrive at the hospital in this order and the priority they are assigned is shown in parentheses:

If you were to place them into a patient queue and dequeue them, they would come out in this order:

• Ford, Anat, Rein, Wu, Sasha, Ben

Binary Heap

The patient queue is a specific application of a well-known abstract data type called a priority queue. You can think of a priority queue as a sorted queue where the elements are sorted by priority. But the priority queue need not internally store its elements in sorted order; all that matters is that the dequeue operation accesses the frontmost element (which will be the minimum priority). As we will see, this difference between the external expected behavior of the priority queue and its true internal state can lead to an interesting implementation.

The priority queue implementation you are to write stores the elements into an unfilled array. The array elements are organized into an arrangement called a binary heap. A binary heap that is arranged to put the minimum priority element frontmost is classified as a minheap.

As discussed in lecture, a binary heap is an array that obeys a heap ordering property. Each index i is thought of as the "parent" of the two "child" indexes, i * 2 and i* 2 + 1. (To simplify the index math, we strongly suggest leaving index 0 unused and starting the data at index 1.) A parent is in front of its children in the queue. For a min-heap, this means the parent must have a smaller priority than its children, i.e. it is the minimum of the "family".

One very desirable feature of a binary heap is that the frontmost element (the one that should be returned by peek or dequeue) is always located at index 1. For example, suppose we added the six patients from the bulleted list in the previous section to a min-heap. The frontmost element is stored at index 1; that element is "Ford" which has minimum priority value 2.

Enqueue

Adding (enqueuing) to a heap is done by placing the new element at the end of the array in the first empty index and then "bubbling up" that element to its proper position according to heap order. Effectively, this starts the new element near the "back" of the queue and jostles its way toward the front by moving ahead of its parent(s) where appropriate. If you would like to see a full trace of the steps necessary to add the preceding six elements to the heap, they are shown below.

The sequence of enqueue operations would produce the following states of the min-heap:

enqueue "Anat" (4)

enqueue "Ben" (9)

enqueue "Sasha" (8)

enqueue "Wu" (7)

(Wu bubbles up from index 4 to 2)

enqueue "Rein" (6)

(Rein bubbles up from index 5 to 2)

enqueue "Ford" (2)

(Ford bubbles up from index 6 to 3 to 1)

The heap order for a min-heap dictates that a parent must be the minimum of the family. If the child just added is smaller than its parent, it belongs in front of it, so the two elements must be swapped. If after swapping, the element that moved ahead is smaller than its new parent, it swaps again. The swapping continues until the element has moved frontward to the proper position and heap order has been restored.

Let's trace adding "Eve" with priority 3 to the above min-heap. She is first placed into index 7:

But this can temporarily break the heap ordering, so we must fix it. An element at index i has its parent at index i/2, so Eve's parent index is 7/2 = 3 (using integer division). Because Eve's priority (3) is smaller than her parent Anat's (4), these two elements are swapped to move Eve in front of Anat. Eve stops bubbling here as her priority (3) is not smaller than her new parent Ford's (2)

The final heap contents after enqueuing "Eve" would be:

Dequeue

Removing (dequeuing) an element from a heap is done by replacing the element at index 1 with the element from the last occupied index of the array and then "bubbling down" that element to the proper position according to heap order. Effectively, this takes an element that was formerly near the "back" of the queue, temporarily puts it in the very front, and then sinks it backward to the proper place by moving it behind its children where appropriate.

Heap order for a min-heap dictates that a parent must be the minimum of the family. If a parent is larger than either/both children, it belongs behind it, so the smaller of the two children must be swapped with the parent. If after swapping, the element that moved behind is still larger than either/both children, it must swap again. The element continues swapping toward the back until it settles in the proper position and heap order has been restored.

Let's trace dequeuing from the min-heap above. The element at index 7, "Anat" (4), is initially used to replace the dequeued element at index 1:

But this can temporarily break the heap ordering, so we must fix it. Anat's priority is compared to her two children at indexes 2 and 3. Because Anat (4) is not smaller than its child Eve (3), Anat must swap with Eve to bring the smaller child in front. No further swapping is needed because Anat's priority (4) is smaller than the priority of its new only child, Sasha (8).

The final heap contents after dequeuing "Ford" would be:

Change Priority

To change the priority of an existing element in a binary heap, you must first loop over the entire heap to find the element. Once found, you set its new priority and then "bubble" the element forward or backward from its current position to restore heap order.

For example, if starting with the min-heap above, changing the priority of Eve to 10 would cause her to move backwards in the queue, first swapping with Anat and then again with Sasha. The final heap contents would be:

A key benefit of using a binary heap implementation for a priority queue is efficiency. The peek operation is very fast since the frontmost element is always stored at index 1. The "bubbling" process moves an out-of-place element to its proper position in step sizes of increasing powers of 2, which means only a few steps are needed to cover a lot of ground. This makes the enqueue and dequeue operations both fast.

Patient Class

We supply you with a Patient type in Patient.java. This type represents a single entry in the queue. Each patient stores information about one patient, including a String for the patient's name and an integer for their priority.

Since the class is small and simple, it uses public member variables that you can access directly. (You should not have public member variables in your PatientQueue class).

Required Methods

Your PatientQueue class must support the following operations. The header for each member function must match those specified below. Do not change the parameter or return types or function names.

Priority Ties & Constraints

• If there is ever a tie in priority, break ties by comparing the strings themselves, treating a string that comes earlier in the alphabet as being in front (e.g. "Anat" before "Ben"). Do not make assumptions about the string lengths.
• Duplicate patient names and priorities are allowed in your queue. The changePriority operation should affect only a single occurrence of a patient's name (the first one found). If the queue contains other occurrences of that same name, a single call to changePriority shouldn't affect them all.
• You should not make unnecessary passes over the queue. For example, when enqueuing an element, a poor implementation would be to traverse the entire queue. The point of using a binary heap is that you should not need to do that.
• You are not allowed to use a sort function or library to arrange the elements of your queue.
• You are not allowed to use any Java collections. You may only use an array.
• You are not allowed to create any temporary or auxiliary data structures (such as addi tional arrays) anywhere in your code, other than when you are resizing to a larger array on an enqueue operation. You must implement all behavior using only the one heap array of patients as specified.