Homework SoursePriority Queue as a Heap Array Emergency Room Patient Admitt
Priority Queue as a Heap Array
Emergency Room Patient Admittance
Objectives
• Build a priority queue as a heap stored in an array
• Dequeue the next priority item and maintaining the heap
For this assignment, you will be implementing a class of your own: a priority queue,
which is a variation on the standard queue. The standard queue processes element
in the first-in, first-out (\"FIFO\") manner typical of ordinary waiting lines. Queues can
be handy, but a FIFO strategy isn\'t always what\'s needed. A hospital emergency
room, for example, needs to schedule patients according to priority. A patient with a
more critical problem will pre-empt others even if they have been waiting longer.
This is a priority queue, where elements are prioritized relative to each other and
when asked to dequeue one, it is the highest priority element in the queue that is
removed.
The priority queue will store a collection of structs that keep track of the patient
name and an integer for the priority. Smaller integers are considered higher priority
than larger ones and are dequeued ahead of larger values.
The header file is provided with a struct to maintain the patient information and a
class to maintain the priority queue. In this example, assume all priority numbers
are unique (in a real ER program, the numbers may be from 1 to 10 plus the date/time
stamp to determine who came in first when multiple have the same priority).
Specifications
• Use the provided header file – do not change in any way!
• Test your program with the provided driver program – without changing the
driver program your output should match what is provided below.
Expected Output
From the provided driver program, your output should appear as follows:
Adding 22 Lila
===
Patients Waiting
[22] Lila
===
Processing 22 Lila
===
NEXT! - Lila
===
Patients Waiting
No one waiting!
===
Adding 3 Liz
===
Patients Waiting
[3] Liz
===
Adding 19 Xylo
===
Patients Waiting
[3] Liz
[19] Xylo
===
Adding 20 Zedder
===
Patients Waiting
[3] Liz
[19] Xylo
[20] Zedder
===
Adding 15 Ratner
===
Patients Waiting
[3] Liz
[15] Ratner
[20] Zedder
[19] Xylo
===
Adding 7 Tattle
===
Patients Waiting
[3] Liz
[7] Tattle
[20] Zedder
[19] Xylo
[15] Ratner
===
Adding 6 Sassy
===
Patients Waiting
[3] Liz
[7] Tattle
[6] Sassy
[19] Xylo
[15] Ratner
[20] Zedder
===
Adding 2 Elle
===
Patients Waiting
[2] Elle
[7] Tattle
[3] Liz
[19] Xylo
[15] Ratner
[20] Zedder
[6] Sassy
===
Adding 1 Alph
===
Patients Waiting
[1] Alph
[2] Elle
[3] Liz
[7] Tattle
[15] Ratner
[20] Zedder
[6] Sassy
[19] Xylo
===
Adding 5 Ophra
===
Patients Waiting
[1] Alph
[2] Elle
[3] Liz
[5] Ophra
[15] Ratner
[20] Zedder
[6] Sassy
[19] Xylo
[7] Tattle
===
Adding 4 Mommy
===
Patients Waiting
[1] Alph
[2] Elle
[3] Liz
[5] Ophra
[4] Mommy
[20] Zedder
[6] Sassy
[19] Xylo
[7] Tattle
[15] Ratner
===
Processing 1 Alph
===
NEXT! - Alph
9 patients currently waiting.
Adding 1 Aso
===
Patients Waiting
[1] Aso
[2] Elle
[3] Liz
[5] Ophra
[4] Mommy
[20] Zedder
[6] Sassy
[19] Xylo
[7] Tattle
[15] Ratner
===
Adding 8 Vinnie
===
Patients Waiting
[1] Aso
[2] Elle
[3] Liz
[5] Ophra
[4] Mommy
[20] Zedder
[6] Sassy
[19] Xylo
[7] Tattle
[15] Ratner
[8] Vinnie
===
We\'re CLOSING! Deleting patient queue!
Removing Aso from the queue.
Removing Elle from the queue.
Removing Liz from the queue.
Removing Ophra from the queue.
Removing Mommy from the queue.
Removing Zedder from the queue.
Removing Sassy from the queue.
Removing Xylo from the queue.
Removing Tattle from the queue.
Removing Ratner from the queue.
Removing Vinnie from the queue.
the provided driver -- Driver.cpp
#include <iostream>
#include \"PatientQueue.hpp\"
using namespace std;
void processNextPatient(PatientQueue* queue);
int main()
{
PatientQueue *queue = new PatientQueue();
queue->enqueue(22, \"Lila\");
processNextPatient(queue);
queue->printList();
processNextPatient(queue);
queue->enqueue(3, \"Liz\");
queue->enqueue(19, \"Xylo\");
queue->enqueue(20, \"Zedder\");
queue->enqueue(15, \"Ratner\");
queue->enqueue(7, \"Tattle\");
queue->enqueue(6, \"Sassy\");
queue->enqueue(2, \"Elle\");
queue->enqueue(1, \"Alph\");
queue->enqueue(5, \"Ophra\");
queue->enqueue(4, \"Mommy\");
processNextPatient(queue);
cout << queue->size() << \" patient\" << (queue->size()==1?\"\":\"s\") << \" currently waiting.\" << endl;
queue->enqueue(1, \"Aso\");
queue->enqueue(8, \"Vinnie\");
delete queue;
return 0;
}
void processNextPatient(PatientQueue* queue)
{
if (queue == NULL)
{
cout << \"No one waiting!\" << endl;
}
else if (!queue->isEmpty())
{
Patient *next = queue->dequeue();
cout << \"===\ NEXT! - \" << next->name << endl;
delete next;
}
}
the provided hpp file -- PatientQueue.hpp
//using namespace std;
struct Patient
{
int priority;
std::string name;
Patient(int _priority, std::string _name)
{
priority = _priority;
name = _name;
}
};
class PatientQueue
{
public:
PatientQueue();
~PatientQueue(); // release memory and delete queue
int size();
bool isEmpty();
void enqueue(int priority, std::string name);
Patient* dequeue(); // returns pointer to patient record and removes from array
void printList(); // print the array
private:
void swap(int index1, int index2); // swap the contents in the array
Patient *waitlist[100];
int lastIndex;
};
PriorityQueue.cpp I have made thus far
#include \"PatientQueue.hpp\"
#include <iostream>
using namespace std;
PatientQueue::PatientQueue()
{
rear = NULL;
front = NULL;
}
PatientQueue::~PatientQueue() // release memory and delete queue
{
//stuff
}
int PatientQueue::size()
{
//stuff
}
bool PatientQueue::isEmpty()
{
//stuff
}
void PatientQueue::enqueue(int priority, std::string name)
{
Patient *temp = new Patient;
temp->priority = name;
temp->next = NULL;
if(front == NULL)
{
front = temp;
}
else
{
rear->next = temp;
}
rear = temp;
}
PatientQueue::Patient* dequeue() // returns pointer to patient record and removes from array
{
Patient *temp = new Patient;
if(front == NULL)
{
cout<<\"\ Queue is Empty\ \";
}
else
{
temp = front;
front = front->next;
cout<<\"The data Dequeued is \"<<temp->priority;
delete temp;
}
}
void PatientQueue::printList() // print the array
{
Patient *p = new Patient;
p = front;
if(front == NULL)
{
cout<<\"\ Nothing to Display\ \";
}
else
{
while(p!=NULL)
{
cout<<endl<<p->priority;
p = p->next;
}
}
}
void PatientQueue::swap(int index1, int index2) // swap the contents in the array
{
int temp = list[index1];
list[index1] = list[index2];
list[index2] = temp;
}
PatientQueue::Patient *waitlist[100]
{
//stuff
}
int PatientQueue::lastIndex
{
//stuff
}
Solution
Here is the PatientQueue.cpp file contents
#include \"PatientQueue.hpp\"
#include <iostream>
using namespace std;
PatientQueue::PatientQueue()
{
lastIndex = 0; //initialize the count
}
PatientQueue::~PatientQueue() // release memory and delete queue
{
for(int i = 0 ; i < lastIndex ; i++)
{
cout<<\"Removing \"<<waitlist[i]<<\" from the queue.\"<<endl;
delete waitlist[i];
}
}
int PatientQueue::size()
{
return lastIndex ;
}
bool PatientQueue::isEmpty()
{
return lastIndex == 0;
}
void PatientQueue::enqueue(int priority, std::string name)
{
cout<<\"Adding \"<<priority<<\" \"<<name<<endl;
//first we store the new patient in the end of queue,
waitlist[lastIndex] = new Patient(priority,name);
//now we sort rest of the array leaving out the last position and swapping any patients that are lower in priority with the last patient
for(int i=0;i<lastIndex;i++)
if(waitlist[i]->priority > waitlist[lastIndex]->priority)
swap(i,lastIndex);
lastIndex++;
cout<<\"===\"<<endl;
printList();
}
void PatientQueue::swap(int index1,int index2) //swap the contents of index1 and index2
{
Patient *temp=waitlist[index1];
waitlist[index1]=waitlist[index2];
waitlist[index2]=temp;
}
Patient* PatientQueue::dequeue() // returns pointer to patient record and removes from array
{
if(isEmpty())
return NULL;
//remove the first element from queue and then move rest of them upwards
Patient *next=waitlist[0];
for(int i=0;i<size();i++)
waitlist[i]=waitlist[i+1];
lastIndex--; //reduce the count since we have removed one
return next;
}
void PatientQueue::printList() // print the array
{
cout<<\"Patients waiting \"<<endl;
if(isEmpty())
cout<<\"No one waiting\"<<endl;
else
{
for(int i=0;i<size();i++)
cout<<\"[\"<<waitlist[i]->priority<<\"] \"<<waitlist[i]->name<<endl;
}
}
From the problem description, it indicates that patients queue should be sorted on priority .
But somehow I dont understand how the elements are getting stored the array in the output shown. It really looks random. Till the point \"Adding 15 Ratner\", the array looks sorted on priority, but beyond that it really confusing how they are getting shuffled. If you could explain the logic , I could code the enque method accordingly. Thanks
By the way, the class does not use next pointer, they maintain an array of pointers in which we need to store the new patients pointer. So I have modified accordingly.
