The most common use of Max-Heap priority queues is in simulation. A simulation o
ID: 3592332 • Letter: T
Question
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 asked to develop a simple program 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:
1. The dynamic scheduling software application MUST be written in Java and is required to use Max-Heap Priority Queue approach.
2. 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.
3. 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.)
4. The software MUST at least contains the following functions:
1. Max-Heapify()
2. Build-Max-Heap()
3. Heapsort()
4. Max-Heap-Insert()
5. Heap-Extract-Max
6. Heap-Increase-Key
7. Heap-Maximum
Explanation / Answer
import java.util.Arrays;
public class HeapSort {
static void Exchange(int[] A, int x, int y) //Does a Swap
{
int temp = A[x-1]; //Place A[x-1] into temp
A[x-1] = A[y-1]; // Place A[y-1] into A[x-1]
A[y-1] = temp; // Place temp into A[y-1]
}
public static void HeapSort(int[] A){ //Heap sort Method
BuildMaxHeap(A); //First Step is to Build a Heap
int heapSize = A.length;
for(int i = A.length; i >= 2; i--){ //Once build heap is done, start from last element down to 2
Exchange(A,1,i); //Swap last element with root
heapSize--; //Decrease the size of heap by 1
MaxHeapify(A,1,heapSize); //Again do a heapify by call root
}
}
public static void BuildMaxHeap( int [] A){ //Build Heap Method
for(int i = A.length/2;i>=1;i--) { //Start with the first Internal node and move down to the root
MaxHeapify(A,i,A.length); //Max Heapify it
}
}
public static void MaxHeapify(int [] A, int i,int heapSize){ //Max Heapify Method
int l = 2*i; //Get the index of element to its left
int r = (2*i)+1; //Get the index of element to its right
int largest;
if (l <= heapSize && A[l-1] > A[i-1]) { //Check if the element at left is greater than its parent
largest = l; //assign largest to left index
}
else {
largest = i; //otherwise assign largest to parent index
}
if( r <=heapSize && A[r-1] > A[largest-1]){ //Check if the element at right is greater than its parent
largest = r; //assign largest to right index
}
if(largest != i) //If largest is not equal to parent
{
Exchange(A, i, largest); //Exchange largest with the parent
MaxHeapify(A, largest, heapSize); //Do a Max heapify by passing the largest element
}
}
public static int HeapExtractMax(int [] A, int heapSize){
if (heapSize <= 0)
return Integer.MAX_VALUE;
if (heapSize == 1)
{
heapSize--;
return A[0];
}
int root = A[0];
A[0] = A[heapSize-1];
heapSize--;
MaxHeapify(A,1,heapSize);
return root;
}
public static void main(String[] args) {
int[] random = new int[]{2, 9, -11, 8, 5, 9001, 3};
HeapSort(random); //Call to the function HeapSort
System.out.println("Expect random to be: -11, 2, 3, 5, 8, 9, 9001: " + Arrays.toString(random));
int[] LowtoHight = new int[]{2, 9, -11, 8, 5, 9001, 3};
HeapSort(LowtoHight); //Call to the function HeapSort
System.out.println("Expect LowtoHight to be: -11, 2, 3, 5, 8, 9, 9001: " + Arrays.toString(LowtoHight));
int[] HighttoLow = new int[]{9001, 9, 8, 5, 3, 2, -11};
HeapSort(HighttoLow); //Call to the function HeapSort
System.out.println("Expect HighttoLow to be: -11, 2, 3, 5, 8, 9, 9001: " + Arrays.toString(HighttoLow));
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.