Assignment 4: Priority Queuing
Data Structures and Analysis of Algorithms
Objectives:
To strengthen student’s knowledge of heaps and priority queuing
To give student experience in writing Object Oriented code
Background:
Queuing is a problem which is commonly encountered in stores, movie theaters, IT services,
and hospitals; many people or problems waiting in line to be addressed in an orderly and
controlled fashion. Basic queues address the problem based solely on the relative positions of
the object in the queue; the first object in the queue is the first object out of the queue. Basic
queues are well suited to model simple lines like the ones found in stores, the DMV, and movie
theaters. When other parameters such as degree of urgency impact the order in which the
objects in the queue must be addressed, priority queuing is the answer. Priority queues pull
objects from the queue based on measure of precedence known as priority. IT services and
emergency rooms in hospital rooms often employ forms of priority queuing.
Heaps are commonly used to implement a priority queues. The reason is because all elements in
the heap are organized relative to a given heap order property. This property requires that items
retrieved from the heap are either the smallest value in the heap (called a min heap), or the
largest value in the heap (called a max heap). In other words, when retrieving data from a min
heap, the element with the smallest value over all elements in the heap has priority and is
removed first; the same holds for a max heap. The heap data structure is a complete binary tree,
implemented as a static or dynamic array, where each subtree in the tree also follow the heap
order property (i.e. the root is either the minimal or maximal value in that subtree).
This exercise will focus on the potential use of priority queuing in emergency rooms. Hospital
emergency rooms often divide the severity of their cases into five general levels from most
urgent to least urgent: Code, Critical, Urgent, Non-urgent disabled, Ambulatory.
The Code level “refers to someone who has suffered cardiac arrest outside of the hospital or
someone whose vital signs crash within the emergency department [1].” It also refers to “
people with gunshot or stab wounds with possible vital organ involvement and/or altered or
absent vital signs [1].” Patients at the Code level bypass the management system and are taken
directly to the next available trauma bed.
The Critical level refers to “a person with stable vital signs who is exhibiting symptoms or who
gives a history that clearly delineates a life-threatening condition. This might be a patient with
chest pain, shortness of breath, and profuse sweating (diaphoresis). This also would include
people who have a history of vomiting blood, multiple traumas with head injury, or a gunshot or
stab wound, as well as asthmatics, diabetics with low blood sugar or extremely high blood
sugar, and the like. [1]”
The Urgent level refers to “patients with serious conditions requiring medical intervention
within two hours … These are people with abdominal pain, high fever and/or productive cough,
deep lacerations with bleeding under control, closed fractures with deformity, and so on [1].”
The Non-urgent disabled level refers to “individuals, unable to walk or remain in a chair, … for
whom the triage nurse determines that up to a four-hour wait is clinically acceptable [1].” These
include patients with herniated discs as well as nursing home patients with dislodged catheters
and feeding tubes.
The Ambulatory level refers to patients “who do not need emergency care but are there anyway
with colds, toothaches, headaches, bumps, bruises, abrasions, small lacerations, skin rashes, and
so on [1].”
It is not uncommon for multiple patients to have complaints at the same level of severity. When
this happens, priority is given to the patient that arrived in the emergency room first.
Instructions:
Using heaps and priority queuing, design and implement an emergency room simulator. The
purpose of the simulator is to model the daily flow of patients through an emergency room. The
system must be able to store the patient’s name and complaint and then be able to prioritize their
access based on the severity of their complaint and the order they entered the ER.
A priority queue implemented with a heap won’t preserve the order in which patients are
entered into the simulator; we will need to store additional data to indicate when the patient
arrived in relation to the other patients in the ER.
The system should support two modes: a build mode and a run mode. The system starts in build
mode.
The build mode allows the user to populate the emergency room with any number of patients
prior to entering run mode. Build mode should support the following commands:
1. Add – prompts the user to add a new patient and health complaint. The priority queue hasn’t
been built yet, so patients added during build mode should be added directly to the end of the
patient list.
2. Run – switch to run mode. Switching to run mode turns the list of patients into a priority
queue.
3. Exit – exit the program
The run mode allows the user to interact with the priority queue. Run mode should support the
following commands:
1. Add – prompts the user to add a new patient and health complaint into the priority queue.
2. Next – displays the next patient to be seen in the ER and updates the priority queue.
3. Peek – displays the next patient to be seen in the ER without removing them from the priority
queue.
4. Build – switch to build mode.
5. Exit – exit the program
| patient | |||
| Attributes (partial list, other attributes might be necessary) | |||
| Name | Data Type | Purpose | |
| Name | String | Name of patient | |
| Complaint | String | Patient’s Complaint | |
| Priority | Integer | Priority value for complaint | |
| Ticket | Integer | Unique number representing when the patient arrived | |
| Methods (partial list, other methods might be necessary) | |||
| Name | Return Type | Parameter List | Purpose |
| Constructor | None | None | Empty constructor that creates a basic patient with an ambulatory level complaint and a ticket of -1 |
| Constructor | None | Name: String Complaint: String Priority: Integer Ticket: Integer |
Constructor that creates a patient with name, complaint, priorty, and ticket set to the specified values |
| ER_queue | |||
| Attributes (partial list, other attributes might be necessary) | |||
| Name | Data Type | Purpose | |
| heap | vector<patient *> | List of patients, complaints, and priority levels | |
| mode | Boolean | Run mode = true, Build mode = false | |
| next_ticket | Integer | The next ticket number to be assigned to a patient | |
| Methods (partial list, other methods might be necessary) | |||
| Name | Return Type | Parameter List | Purpose |
| Constructor | None | None | Empty constructor that creates an empty priority queue in Build mode. |
| Insert | Boolean | Name: String Complaint: String Priority: Integer |
Creates a patient with attributes Name, Complaint, Priority and inserts them into the vector heap. This method will adjust the priority queue if ER_queue is in Run mode. |
| Peek | Patient * | None | Returns the contents of the heap’s root without altering them |
| Remove | Patient * | None | When the ER_Queue is in Run mode, removes the top most value in the priority queue and returns it |
| Build_Heap | None | None | Turns the contents of the vector heap into a proper heap; sets mode to true |
| Set_Mode | None | Boolean | Sets the mode of the ER_queue. True = run mode; False = build mode |
| Get_Mode | Boolean | None | Returns the mode of the ER_queue |
Grading Breakdown:
| Point Breakdown | |
| Overall Formatting | |
| The program has a header comment with the required information | 5 |
| Overall readability of the program | 10 |
| Code organization (program is broken into multiple files) | 2 |
| Class Patient | |
| Class Patient is defined | 6 |
| Class Patient defines constructor(s) | 4 |
| Class Patient contains required attributes | 4 |
| Class ER_queue | |
| Class ER_queue is defined | 6 |
| Class ER_queue defines constructor(s) | 4 |
| Class ER_queue defines “insert” method | 4 |
| “insert” method adds new node to end of heap | 3 |
| In Run mode, “insert” method properly restores priority queue | 3 |
| Class ER_queue defines “peek” method | 4 |
| Class ER_queue defines “remove” method | 4 |
| In Run mode, “remove” method properly updates priority queue | 3 |
| Main program | |
| user interface recognizes and handles “add” command | 3 |
| user interface recognizes and handles “next” command | 3 |
| user interface recognizes and handles “run” command | 3 |
| user interface recognizes and handles “build” command | 3 |
| user interface recognizes and handles “peek” command | 3 |
| user interface recognizes and handles “exit” command | 3 |
| Function and Interface | |
| Program responds as expected to test inputs/data | 10 |
| User interface is easy to understand and functions correctly | 10 |
| Total | 100 |
| Penalties | |
| program fails to compile | -50 |
| Late penalty |
| program is less than 24 hours late | -30 |
| program is greater than or equal to 24 hours late | -100 |
Header Comment:
At the top of each program, type in the following comment:
/*
Student Name: <student name>
Student NetID: <student NetID>
Compiler Used: <Visual Studio, GCC, etc.>
Program Description:
<Write a short description of the program.>
*/
Example:
/*
Student Name: John Smith
Student NetID: jjjs123
Compiler Used: Visual Studio
Program Description:
This program prints lots and lots of strings!!
*/
Assignment Information:
Due 11/20/2018
Files Expected:
Main.cpp – file containing the interface for interacting with the grasshopper class
ER_queue.h – file containing definitions of the patient and er_queue class
References:
[1] T. A. Sharon, “Standards of Care in the Emergency Room: The Emergency Waiting
Game,” LinkedIn: Log In or Sign Up. [Online]. Available: https://www.linkedin.com/pulse/
standards-care-emergency-room-waiting-game-sharon-r-n-m-p-h-. [Accessed: 15-Oct-
2018].
The post Data Structures and Analysis of Algorithms appeared first on My Assignment Online.