Priority Queue

Emergency Room Scheduling

Objectives

Implement a Priority Queue using a Heap, backed by an array

Add element to Heap

Remove element from Heap

Background

Hospital Emergency Room Waiting List

A hospital emergency room does not see patients on a first-come first-served (FIFO) basis. Rather, the most urgent patients are seen before patients whose injuries are less severe or non-life-threatening. You will implement a priority queue such that patients with the most severe injuries are admitted before those who have less severe injury. For each patient in the priority queue, the following information is stored:

Name of patient

Injury Severity: an integer, higher values represent higher priorities for admission.

Treatment Time: estimated time required to treat patient once patient is admitted

Program Specifications

Your priority queue will be implemented in a class based on the provided PriorityQueue.hpp (download from moodle). You will also implement a driver program with menu functionality.

Your program will read in the maximum queue size and the name of a text file containing patient information from the command line

Example:

./a.out 10 patientFile.txt

The first command line argument corresponds to the maximum queue size. If the priority queue is full and more patients attempt to join the queue, they will be sent to another hospital.

The second command line argument is the name of a text file containing patient information. Each patients information is on one line and the information fields are separated by a space. Patient names will not have spaces in the name. Lines will be ordered such as:

Example: name injurySeverity treatmentTime

Greg 10 100 Tom 5 120

Menu: In your driver function, display a menu with the following options:

1. Get Patient Information from File

When this option is selected, patient information is read in from the text file provided via command line argument. This option will fill the priority queue with patient information stored in the text file. If the priority queue is empty when this option is chosen, patients in the file are added to the queue. If the priority queue is not empty when this option is chosen, patients in the file are added to the pre-existing priority queue. If the queue reaches maximum capacity during this operation, remaining patients will be sent to another hospital.

2. Add Patient to Priority Queue

If the priority queue is not full:

When the user selects this option, they should be prompted for the name of the patient, patient's injury severity, and expected treatment time. This patient is then inserted into the priority queue based on injury severity. If two patients have an identical injury severity, give priority to the patient with shorter treatment time. We assume that two patients cannot both have the same injury severity and treatment time.

If the priority queue is full:

The patient will be sent to another hospital.

3. Show Next Patient

Displays information for the patient at the head of the priority queue, but does not dequeue the patient.

4. Admit Next Patient

Removes the patient at the head of the priority queue. If the priority queue is not empty, there is no output. If the queue is empty, notifies user that the queue is empty.

Total wait time for admitted Patient N = (Patient 0 treatment time + Patient 1 treatment time + ... + Patient N-1 treatment time).

Total treatment time for admitted Patient N = treatment time for patient N + Total wait time for Patient N

5. Process Entire Queue

When the user selects this option, patients will be dequeued until the priority queue is empty. As patients are removed from the queue (admitted to the ER), display their name, as well as the total amount of time that the patient had to wait to be admitted. For simplicity, assume that the first patient admitted did not have to wait, and that the ER has only one doctor. Therefore, patient 1's total wait time is equal to patient 0's treatment time. Total wait time for Patient N = (Patient 0 treatment time + Patient 1 treatment time + ... + Patient N-1 treatment time).

Total treatment time for Patient N = treatment time for patient N + Total wait time for Patient N

When this option is selected, Total treatment time for each patient is calculated from information about patients in the queue, ignoring any patients that have been manually dequeued using Admit Next Patient above.

6. Quit

When the user selects this option, the program exits cleanly.

Output: All output will be generated in the main function. See Expected Output section.

Class Implementation: Your class will store the priority queue in an array. See lecture notes for information on how to implement a binary heap in an array for implementation tips. Store the node with highest priority at index 1 of the array, not index 0. Since the priority queue is an array of PatientNodes, not pointers to PatientNodes, you do not need to create new nodes with the new keyword.

Implement the following methods for your PriorityQueue class:

1. PriorityQueue

Perform all necessary actions to instantiate the class object.

2. ~PriorityQueue

Perform all necessary actions to destruct the class object.

3. enqueue

Insert a patient into the priority queue. Patients are given priority based on injury severity, with higher ranks of injury severity having priority over lower ranks of injury severity (rank 9 has higher priority than rank 1). Be sure to maintain the heap properties. If two patients have identical injury severity, give priority to the patient with the shorter treatment time. We assume that two patients cannot have both same injury severity and treatment time.

4. peekName

Returns the name of the patient at the front of the priority queue as a string, but does not dequeue.

5. peekInjurySeverity

Returns the injury severity of the patient at the front of the priority queue as an int, but does not dequeue.

6. peekTreatmentTime

Returns the treatment time of the patient at the front of the priority queue as an int, but does not dequeue.

7. dequeue

Removes the patient at the front of the priority queue. Be sure to maintain the heap properties.

8. isFull

Returns true if the priority queue is full, false otherwise.

9. isEmpty

Returns true if the priority queue is empty, false otherwise.

10. repairUpward

Used in the enqueue() method to maintain heap properties of the priority queue. (Hint: In enqueue method, call repairUpward on the last item)

Used to maintain heap properties.

11. repairDownward

Used in the dequeue() method to maintain heap properties of the priority queue. (Hint: In dequeue method, call repairDownward on the first item in the priority queue which is at index 1)

Used to maintain heap properties.

Expected Output

Used for formatting purposes only. Modify as needed to match your driver implementation.

Display menu

cout << "======Main Menu======" << endl;

cout << "1. Get Patient Information from File" << endl;

cout << "2. Add Patient to Priority Queue" << endl;

cout << "3. Show Next Patient" << endl;

cout << "4. Admit Next Patient" << endl;

cout << "5. Process Entire Queue" << endl;

cout << "6. Quit" << endl;

Get Patient Information from File

//if priority queue is full, or becomes full during the process of

//enqueueing all patients in the file, print once regardless of how

//many patients are turned away

cout << "Priority Queue full. Send remaining patients to another hospital."

<< endl;

Add Patient to Priority Queue

//if priority queue is full

cout << "Priority Queue full. Send Patient to another hospital." << endl;

//else

cout << "Enter Patient Name:" << endl;

cout << "Enter Injury Severity:" << endl;

cout << "Enter Treatment Time:" << endl;

Show Next Patient

//if priority queue is empty

cout << "Queue empty." << endl;

//else

cout << "Patient Name: " << patientName << endl;

cout << "Injury Severity: " << patientInjurySeverity << endl;

cout << "Treatment Time: " << patientTreatmentTime << endl;

Admit Next Patient

//if priority queue is empty

cout << "Queue empty." << endl;

Process Entire Queue

//if priority queue is empty

cout << "Queue empty." << endl;

//else, for all patients in queue:

cout << "Name: "<< patientName << " - Total Wait Time: " << totalWaitTime << endl;

Quit

cout << "Goodbye!" << endl;

Sample Program Execution:

$./a.out 10 patientFile.txt

will execute the program with a maximum queue size of 10 and use patientFile.txt as the source of patient information. Output of this execution (max queue size = 10, reading patient information for 12 patients from patientFile.txt, and processing entire queue) is as follows:

======Main Menu======

1. Get Patient Information from File

2. Add Patient to Priority Queue

3. Show Next Patient

4. Admit Next Patient

5. Process Entire Queue

6. Quit

1

Priority Queue full. Send remaining patients to another hospital.

======Main Menu======

1. Get Patient Information from File

2. Add Patient to Priority Queue

3. Show Next Patient

4. Admit Next Patient

5. Process Entire Queue

6. Quit

5

Patient Name: Greg - Total Wait Time: 0

Patient Name: Hank - Total Wait Time: 100

Patient Name: Irma - Total Wait Time: 190

Patient Name: Juliet - Total Wait Time: 270

Patient Name: Frank - Total Wait Time: 340

Patient Name: Eric - Total Wait Time: 390

Patient Name: Dan - Total Wait Time: 430

Patient Name: Charles - Total Wait Time: 460

Patient Name: Bob - Total Wait Time: 480

Patient Name: Adam - Total Wait Time: 490

======Main Menu======

1. Get Patient Information from File

2. Add Patient to Priority Queue

3. Show Next Patient

4. Admit Next Patient

5. Process Entire Queue

6. Quit

6

Goodbye!