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