Priority Queue as a Heap Array Emergency Room Patient Admitt

Priority Queue as a Heap Array: Emergency Room Patient Admittance

• Build a priority queue as a heap stored in an array
• Dequeue the next priority item and maintaining the heap

• Use the provided header file – do not change in any way!
• Test your program with the provided driver program.

I need to implement a class of my 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).

Header File:

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;
};

Driver:

#include
#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;
   }
}

PatientQueue.hpp

#include <iostream>
class Patient{
int priority;
std::string name;
public:
int getPriority();
void setPriority(int);
std::string getName();
void setName(std::string);
};

class PatientQueue
{
public:
PatientQueue(){
waitlist = new Patient[100];
}
~PatientQueue(){
delete []waitlist;
} // release memory and delete queue
int size();
bool isEmpty();
void enqueue(int,std::string);
Patient dequeue(); // returns pointer to patient record and removes from array
void printList(); // print the array
private:
void maintainHeap(int);
void minify(int);
bool greater(int , int);
void swap(int, int); // swap the contents in the array
Patient *waitlist;
int lastIndex;
};

Driver.cpp

#include <iostream>
#include \"PatientQueue.hpp\"
using namespace std;

void Patient::setName(string name){
this->name = name;
}

string Patient::getName(){
return name;
}

void Patient::setPriority(int priority){
this->priority = priority;
}

int Patient::getPriority(){
return priority;
}

int PatientQueue::size(){
return lastIndex;
}

bool PatientQueue::isEmpty(){
return size() == 0;
}

void PatientQueue::swap(int i, int j){
Patient temp = waitlist[i];
waitlist[i] = waitlist[j];
waitlist[j] = temp;
}

// you can customize this function now, currently its comparing priority only you can add time, name, age, disease etc
bool PatientQueue::greater(int i, int j){
if(waitlist[i].getPriority() >= waitlist[j].getPriority()){
return true;
}
return false;
}
void PatientQueue::minify(int n){
// just usual heap property, if parent is greater than child swap them
// do until you reach the root
while (n > 1 && greater(n/2, n)) {
swap(n, n/2);
n = n/2;
}
}

//maintain the heap property after deletion of element or deque
void PatientQueue::maintainHeap(int n){
while (2*n <= lastIndex) {
int j = 2*n;
if (j < lastIndex && greater(j, j+1)) j++;
if (!greater(n, j)) break;
swap(n, j);
n = j;
}
}

void PatientQueue::enqueue(int priority, string name){
waitlist[++lastIndex].setPriority(priority);
waitlist[lastIndex].setName(name);
minify(lastIndex);

}

Patient PatientQueue::dequeue(){
if (isEmpty()){
cout << \"Queue is empty so can\'t delete element\";
exit(1);
}
swap(1, lastIndex);
Patient min = waitlist[lastIndex--];
maintainHeap(1);
return min;
}
void PatientQueue::printList(){

}

void processNextPatient(PatientQueue* queue);
int main()
{
PatientQueue *queue = new PatientQueue();
queue->enqueue(22, \"Lila\");
processNextPatient(queue);
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\");
cout << queue->size() << \" patient\" << (queue->size()==1?\" are \":\"s are \") << \" currently waiting.\ \" << endl;
queue->enqueue(1, \"Aso\");
queue->enqueue(8, \"Vinnie\");
while(!queue->isEmpty()){
processNextPatient(queue);
}
return 0;
}
void processNextPatient(PatientQueue* queue){
if(!queue->isEmpty()){
Patient p = queue->dequeue();
cout <<p.getPriority() << \" , \"<< p.getName() << \" has gone through medical advice\ \";
}
}