Priority Queue

Priority Queue provides the functionality of Heap Data Structure.

→ Before we understand priority queue we must know what is Heap Data Structure:-

HEAP DATA STRUCTURE

→ Heap is a special type of data structure where the root node and
parent node is compared with its left and right children and
arranged according to the children.

TYPES OF HEAPS

-> There are two main types of Heaps:-

• Min Heap

  → In a min-heap, the parent nodes are smaller than or equal to
  their children. So, the smallest element (5) is at the root,
  and each parent node is smaller than its children.

  → Example using diagram:-
  

          5
        /   \\
       9     11
     /  \\   /  \\
   14   18  19  21
  /  \\
  33  17
  

• Max Heap

  -> In max-heap, the parent nodes are larger than or equal to
  their children, So, the largest element (21) is at the root,
  and each parent node is larger than its children.

  -> Example using a diagram:-
  

          21
        /    \\
      19      18
     /  \\    /  \\
   17   11  14   5
  /  \\
  9   3
  

APPLICATION OF HEAP DATA STRUCTURE

• Priority Queue
• Graph Algorithms
• Operating System

QUEUE

when we talk about queues, we often think of a "first-in, first-out" (FIFO) structure, where elements are processed in the order they were added. But what if we need to process elements based on their priority rather than their arrival time? That's where Priority Queues come into play.

Queue Interface Declaration

public interface Queue extends Collection

1. PRIORITY QUEUE

   → A Priority Queue is an abstract data type that stores a
   collection of elements along with their associated
   priorities. Unlike normal Queues, Priority Queue elements
   are retrieved in ascending order.

   → Suppose, we want to retrieve the elements in the ascending
   order. In this case, the head of the priority queue will be
   the smallest element. Once the element is retrieved, the
   next smallest element is the head of the queue.

   → For Example using code:-
   

    import java.util.*;
    public class PriorityQueueDemo{
            public static void main(String[] args){
            PriorityQueue<Integer> pq = new PriorityQueue<>();
            pq.add(4);
            pq.add(3);
            pq.add(2);
            pq.add(1);
            pq.add(5);
            pq.add(9);

    System.out.println("The Element of the Priority Queue is : " + pq);
    //System.out.println("head of the  Queue is : " + pq.peek());
    //System.out.println("Priority Queue Content is : " + pq);
    //System.out.println("head removed : " + pq.poll());
    //System.out.println("Priority Queue content is : " + pq);
    ```



            }
    }

    OUTPUT:-The Element of the Priority Queue is : [1, 2, 3, 4, 5, 9]

    Internally, it follows a min heap and can be visualized as a tree.

    →



    ```
            1
          /   \\
         2     3
       /  \\   /
      4    5  9

    min-heap
    ```




### Methods of Java Queue Interface

| Method | Description |
| --- | --- |
| boolean add(object) | It is used to insert the specified element into this queue and return true upon success. |
| boolean offer(object) | It is used to insert the specified element into this queue. |
| Object remove() | It is used to retrieve and remove the head of this queue. |
| Object poll() | It is used to retrieve and remove the head of this queue or returns null if this queue is empty. |
| Object element() | It is used to retrieve, but does not remove, the head of this queue. |
| Object peek() | It is used to retrieve, but does not remove, the head of this queue, or return null if this queue is empty. |