Priority Queue
Tags: programming, java, queue, codenewbie
Published: 2024-04-23 05:47:19

# 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<E> **extends** Collection<E>

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. |