Instructions
Requirements and Specifications
Source Code
// A binary heap priority queue
public class PatientQueue {
private Patient[] patients;
private int numPatients;
// Create an empty queue
public PatientQueue() {
patients = new Patient[10];
numPatients = 0;
}
// Add a new patient to the queue
public void enqueue(String name, int priority) {
enqueue(new Patient(name, priority));
}
// Add a new patient to the queue
public void enqueue(Patient patient) {
if (numPatients >= patients.length) {
// Expand if out of space
Patient[] temp = new Patient[patients.length * 2];
for (int i = 0; i < patients.length; i++) {
temp[i] = patients[i];
}
patients = temp;
}
patients[numPatients++] = patient;
int currentIndex = numPatients - 1;
// Put higher priorities on top and lower prioritieson the bottom
while (currentIndex > 0) {
int parentIndex = (currentIndex - 1) / 2;
if (patients[currentIndex].getPriority() < patients[parentIndex].getPriority()) {
Patient temp = patients[currentIndex];
patients[currentIndex] = patients[parentIndex];
patients[parentIndex] = temp;
} else {
break;
}
currentIndex = parentIndex;
}
}
// Return the next prioritized patient
public String deque() {
if (numPatients == 0) {
throw new RuntimeException("The queue is empty.");
}
Patient removedPatient = patients[0];
patients[0] = patients[numPatients - 1];
numPatients--;
int parentIndex = 0;
while (parentIndex < numPatients) {
int leftChildIndex = 2 * parentIndex + 1;
int rightChildIndex = 2 * parentIndex + 2;
// Find the max between two children
if (leftChildIndex >= numPatients) {
break;
}
int minIndex = leftChildIndex;
if (rightChildIndex < numPatients) {
if (patients[rightChildIndex].getPriority() < patients[minIndex].getPriority()) {
minIndex = rightChildIndex;
} else if (patients[minIndex].getPriority() == patients[rightChildIndex].getPriority()
&& patients[minIndex].getName().compareTo(patients[rightChildIndex].getName()) < 0) {
minIndex = rightChildIndex;
}
}
// Swap if the current node is less than the minimum
if (patients[minIndex].getPriority() < patients[parentIndex].getPriority()) {
Patient temp = patients[minIndex];
patients[minIndex] = patients[parentIndex];
patients[parentIndex] = temp;
parentIndex = minIndex;
} else if (patients[minIndex].getPriority() == patients[parentIndex].getPriority()
&& patients[minIndex].getName().compareTo(patients[parentIndex].getName()) < 0) {
Patient temp = patients[minIndex];
patients[minIndex] = patients[parentIndex];
patients[parentIndex] = temp;
parentIndex = minIndex;
} else {
break;
}
}
return removedPatient.getName();
}
// Check the next prioritized patient
public String peek() {
if (numPatients == 0) {
throw new RuntimeException("The queue is empty.");
}
return patients[0].getName();
}
// Get the priority number of the next patient
public int peekPriority() {
if (numPatients == 0) {
throw new RuntimeException("The queue is empty.");
}
return patients[0].getPriority();
}
// Update the priority of a patient
public void changePriority(String name, int newPriority) {
for (int i = 0; i < numPatients; i++) {
if (patients[i].getName().equals(name)) {
patients[i].setPriority(newPriority);
}
}
// Re-fix the binary heap
for (int i = numPatients / 2; i >= 0; i--) {
heapify(i);
}
}
// Rearrange the tree making sure higher priority patients
// go on top of the binary heap
private void heapify(int parentIndex) {
if (patients[parentIndex] == null) {
return;
}
int leftChildIndex = parentIndex * 2 + 1;
int rightChildIndex = parentIndex * 2 + 2;
int smallest = parentIndex;
if (leftChildIndex < numPatients) {
if (patients[leftChildIndex].getPriority() < patients[smallest].getPriority()) {
smallest = leftChildIndex;
} else if (patients[leftChildIndex].getPriority() == patients[smallest].getPriority()
&& patients[leftChildIndex].getName().compareTo(patients[smallest].getName()) < 0) {
smallest = leftChildIndex;
}
}
if (rightChildIndex < numPatients) {
if (patients[rightChildIndex].getPriority() < patients[smallest].getPriority()) {
smallest = rightChildIndex;
} else if (patients[rightChildIndex].getPriority() == patients[smallest].getPriority()
&& patients[rightChildIndex].getName().compareTo(patients[smallest].getName()) < 0) {
smallest = leftChildIndex;
}
}
if (smallest != parentIndex) {
Patient temp = patients[parentIndex];
patients[parentIndex] = patients[smallest];
patients[smallest] = temp;
heapify(smallest);
}
}
// Check if queue is empty
public boolean isEmpty() {
return numPatients == 0;
}
// Return the number of elements
public int size() {
return numPatients;
}
// Remove all elements
public void clear() {
numPatients = 0;
}
// Return a string representation of the queue
@Override
public String toString() {
String str = "{";
for (int i = 0; i < numPatients; i++) {
str += patients[i].toString();
if (i + 1 < numPatients) {
str += ", ";
}
}
return str + "}";
}
}