Question

1. A priority queue is an abstract data type which is like a regular queue or some other data structures, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority like scheduler. If two elements have the same priority, they are served according to their order in the queue.

Answer 1

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];

   }

}