Question

1. A priority queue is a special queue that adjusts the location of items based on some priority value. When inserted, a new value is placed in the queue ahead of every other item that has a lower priority than it. This gives us a queue that removes items from the front removing highest priority first, and from items with similar priority the ones that were inserted first. For example, if we inserted the following items with the priority {A, 1}, {B,2}, {C,2}, {D,3}, {E,1} where the lower number is a lower priority, our queue will have the items from front to back: D,B,C,A,E. Using the partial code below, you are to implement the Enqueue method so that the new node is inserted into the appropriate place in the queue based on the priority. (Assume that a higher number is higher priority, for example 0 is lowest and 10 is highest)

class Node<V,P>

{

      public V value;

      public P priority;

      public Node<V,P> next;

     

      Node(V value, P priority)

      {

           this.value = value;

           this.priority = priority;

      }

}

class PriorityQueue<V,P>

{

      private Node<V,P> head;

      private Node<V,P> tail;

     

      ...

      public void Enqueue(V value, P priority)

      {

Answer 1

1). ANSWER :

GIVENTHAT :

The priority is always an integer in our case. If we make even the priority generic, there is no way to compare two generic types so we type cast the priority.

public class PriorityQueue<V,P> {

    private Node<V,P> head;
    private Node<V,P> tail;

    public void Enqueue(V value, P priority){
        // Make a new node with given values.
        Node<V,P> newNode = new Node<>(value, priority);

        // If head is null, make the newNode as head and return.
        if(head == null){
            head = newNode;
            tail = newNode;
            return;
        }

        Node<V,P> cur = head;

        // Make integers from priority as we cannot compare generic types.
        // Please ensure that the priority is a number.
        Integer priority1 = (Integer) (priority);
        Integer priorityHead = (Integer)(head.priority);

        // Check if priority of newNode is greater than priority of head,
        // If it is insert at beginning and update value of head.
        if(priority1 > priorityHead){
            newNode.next = head;
            head = newNode; 
            return;
        }


        // Find the position of newNode in the queue and insert there.
       while(cur != null && cur.next != null){
           
           Integer priority2 = (Integer) (cur.next.priority);

           if(priority1 > priority2){
                Node<V,P> Next = cur.next;
                cur.next = newNode;
                newNode.next = Next;
                return;
           }
           else{
               cur = cur.next;
           }
       }

       // If no appropriate position is found in the middle of queue, insert at end.
       tail.next = newNode;
       tail = newNode;
    }

    // Utility function to print contents of queue.
    void print(){
        Node<V,P> cur = head;
        while(cur != null){
            System.out.println(cur.value + " " + cur.priority);
            cur = cur.next;
        }
        System.out.println("");
    }
    // Driver method to test
    public static void main(String[] args){
        PriorityQueue<Integer,Integer> pq = new PriorityQueue<>();

        pq.Enqueue(1, 5);
        
        pq.Enqueue(100, 0);
        pq.Enqueue(5, 10);
        pq.Enqueue(101, 3);
        pq.Enqueue(5, -1);
        pq.Enqueue(50, 100);
        pq.Enqueue(32, 50);
        pq.print();

    }
    
}

The above program Output : -

As we can see the new entries are inserted in order of priority.