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 .” It also refers to “ people with gunshot or stab wounds with possible vital organ involvement and/or altered or absent vital signs .” 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. ” 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 .” 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 .” 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 .” 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 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 NetID: Compiler Used: Program Description: */ 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:  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-Oct2018].