Answer:
The code is as below whereas the output is attached herewith
Explanation:
package brainly.priorityQueue;
class PriorityJobQueue {
Job[] arr;
int size;
int count;
PriorityJobQueue(int size){
this.size = size;
arr = new Job[size];
count = 0;
}
// Function to insert an element into the priority queue
void insert(Job value){
if(count == size){
System.out.println("Cannot insert the key");
return;
}
arr[count++] = value;
heapifyUpwards(count);
}
// Function to heapify an element upwards
void heapifyUpwards(int x){
if(x<=0)
return;
int par = (x-1)/2;
Job temp;
if(arr[x-1].getPriority() < arr[par].getPriority()){
temp = arr[par];
arr[par] = arr[x-1];
arr[x-1] = temp;
heapifyUpwards(par+1);
}
}
// Function to extract the minimum value from the priority queue
Job extractMin(){
Job rvalue = null;
try {
rvalue = arr[0].clone();
} catch (CloneNotSupportedException e) {
e.printStackTrace();
}
arr[0].setPriority(Integer.MAX_VALUE);
heapifyDownwards(0);
return rvalue;
}
// Function to heapify an element downwards
void heapifyDownwards(int index){
if(index >=arr.length)
return;
Job temp;
int min = index;
int left,right;
left = 2*index;
right = left+1;
if(left<arr.length && arr[index].getPriority() > arr[left].getPriority()){
min =left;
}
if(right <arr.length && arr[min].getPriority() > arr[right].getPriority()){
min = right;
}
if(min!=index) {
temp = arr[min];
arr[min] = arr[index];
arr[index] = temp;
heapifyDownwards(min);
}
}
// Function to implement the heapsort using priority queue
static void heapSort(Job[] array){
PriorityJobQueue object = new PriorityJobQueue(array.length);
int i;
for(i=0; i<array.length; i++){
object.insert(array[i]);
}
for(i=0; i<array.length; i++){
array[i] = object.extractMin();
}
}
}
package brainly.priorityQueue;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class PriorityJobQueueTest {
// Function to read user input
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n;
System.out.println("Enter the number of elements in the array");
try{
n = Integer.parseInt(br.readLine());
}catch (IOException e){
System.out.println("An error occurred");
return;
}
System.out.println("Enter array elements");
Job[] array = new Job[n];
int i;
for(i=0; i<array.length; i++){
Job job =new Job();
try{
job.setJobId(i);
System.out.println("Element "+i +"priority:");
job.setJobName("Name"+i);
job.setSubmitterName("SubmitterName"+i);
job.setPriority(Integer.parseInt(br.readLine()));
array[i] = job;
}catch (IOException e){
System.out.println("An error occurred");
}
}
System.out.println("The initial array is");
System.out.println(Arrays.toString(array));
PriorityJobQueue.heapSort(array);
System.out.println("The sorted array is");
System.out.println(Arrays.toString(array));
Job[] readyQueue =new Job[4];
}
}
