Problem Statements: The most common use of Max-Heap priority queues is in simula
ID: 3591405 • Letter: P
Question
Problem Statements:
The most common use of Max-Heap priority queues is in simulation. A simulation of a hospital waiting room, for example, might prioritize patients waiting based on the severity of their need. For example, doctors in a hospital emergency room often choose to see next the "most critical" patient rather than the one who arrived first.
You are a software engineer and are asked to develop a software application for doctors and administrators to dynamically keep track of treatment scheduling for patients according to priority in the hospital emergency room. A patient with a more critical problem will pre-empt others even if they have been waiting longer.
Programming Requirements:
The dynamic scheduling software application MUST be written in Java and is required to use Max-Heap Priority Queue approach specified in lecture ppt slides and in textbook.
This Max-Heap priority queue, where elements are prioritized relative to each other and when a patient's treatment is finished, the software is asked to Extract-Max(S) one patient with the highest priority in the queue that is removed.
The priority queue implemented in a Max-Heap Tree will store a collection of structs that keep track of the patient's name and an integer for the priority. Larger integers are considered higher priority than smaller ones (Assuming each time there are 20 patients in the MAX-Heap tree only.)
The software MUST at least contains the following functions:
a) Max-Heapify()
b) Build-Max-Heap()
c) Heapsort()
d) Max-Heap-Insert()
e) Heap-Extract-Max
f) Heap-Increase-Key
g) Heap-Maximum
5. Each java file/class/subroutine/function call must contain a header comment at the beginning of it.
Explanation / Answer
Solution,
public class MaximumHeap
{
private int[] Heap;
private int size;
private int Maximumsize;
private static final int FRONT = 1;
public MaximumHeap(int Maximumsize)
{
this.Maximumsize = Maximumsize;
this.size = 0;
Heap = new int[this.Maximumsize + 1];
Heap[0] = Integer.MAX_VALUE;
}
private int Patient(int pos)
{
return pos / 2;
}
private int leftPatient(int pos)
{
return (2 * pos);
}
private int rightPatient(int pos)
{
return (2 * pos) + 1;
}
private boolean isLeaf(int pos)
{
if (pos >= (size / 2) && pos <= size)
{
return true;
}
return false;
}
private void swap(int fpos,int spos)
{
int tmp;
tmp = Heap[fpos];
Heap[fpos] = Heap[spos];
Heap[spos] = tmp;
}
private void MaximumHeapify(int pos)
{
if (!isLeaf(pos))
{
if ( Heap[pos] < Heap[leftPatient(pos)] || Heap[pos] < Heap[rightPatient(pos)])
{
if (Heap[leftPatient(pos)] > Heap[rightPatient(pos)])
{
swap(pos, leftPatient(pos));
MaximumHeapify(leftPatient(pos));
}else
{
swap(pos, rightPatient(pos));
MaximumHeapify(rightPatient(pos));
}
}
}
}
public void insert(int element)
{
Heap[++size] = element;
int current = size;
while(Heap[current] > Heap[Patient(current)])
{
swap(current,Patient(current));
current = Patient(current);
}
}
public void print()
{
for (int i = 1; i <= size / 2; i++ )
{
System.out.print(" Patient : " + Heap[i] + " LEFT PATIENT : " + Heap[2*i]
+ " RIGHT PATIENT :" + Heap[2 * i + 1]);
System.out.println();
}
}
public void MaximumHeap()
{
for (int pos = (size / 2); pos >= 1; pos--)
{
MaximumHeapify(pos);
}
}
public int remove()
{
int popped = Heap[FRONT];
Heap[FRONT] = Heap[size--];
MaximumHeapify(FRONT);
return popped;
}
public static void main(String...arg)
{
System.out.println("The Maximums Heap is ");
MaximumHeap MaximumHeap = new MaximumHeap(20);
MaximumHeap.insert(5);
MaximumHeap.insert(3);
MaximumHeap.insert(17);
MaximumHeap.insert(10);
MaximumHeap.insert(20);
MaximumHeap.insert(19);
MaximumHeap.insert(6);
MaximumHeap.insert(12);
MaximumHeap.insert(9);
MaximumHeap.MaximumHeap();
MaximumHeap.print();
System.out.println("The max value is " + MaximumHeap.remove());
}
}
$javac MaxHeap.java
$java MaxHeap
The Max Heap is
PATIENT: 20 LEFT PATIENT : 19 RIGHT PATIENT :17
PATIENT: 19 LEFT PATIENT : 17 RIGHT PATIENT :12
PATIENT: 17 LEFT PATIENT : 12 RIGHT PATIENT :10
PATIENT: 12 LEFT PATIENT : 10 RIGHT PATIENT :9
The max val is 20
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.