Priority Queues

In general queues follow FIFO (first in first out) ,ie the element inserted first is deleted first from the queue,But priority queue doesnt follow FIFO strictly.

A priority queue is special type of queue in which elements will have priority and are inserted in any order but deleted based on priority , an element with high priority is dequeued before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.

what are the types of priority these elements follow?

1)larger number larger priority

2)smaller number larger priority


so now we got an idea that these can be implemented using heaps !!

Heap is generally preferred for priority queue implementation because heaps provide better performance compared arrays or linked list. 

max heap : larger number larger priority

min heap :  smaller number larger priority




                                            max heap                                                 min heap   



Heaps in C++ 

In C++ the priority_queue container can be used to implement Heaps. The priority_queue in C++ is a built-in container class which is used to implement priority queues easily. This container uses max heap internally to implement a priority queue efficiently. Therefore, it can be also used in-place of max heaps.

This container can also be modified by passing some additional parameters to be used as a Min Heap.

Syntax:
  • For implementing Max Heap:
    priority_queue< type_of_data > name_of_heap;
  • For implementing Min Heap:
    priority_queue< type, vector<type>, greater<type> > name_of_heap;

Methods of priority queue: (
applicable in case of both Max-Heap and Min-heap)
  • priority_queue::empty(): The empty() function returns whether the queue is empty.
  • priority_queue::size(): The size() function returns the size of the queue.
  • priority_queue::top(): This function returns a reference to the top most element of the queue.
  • priority_queue::push(): The push(g) function adds the element ‘g’ at the end of the queue.
  • priority_queue::pop(): The pop() function deletes the first element of the queue.
  • priority_queue::swap(): This function is used to swap the contents of one priority queue with another priority queue of same type and size.












implementation:
// using priority_queue in C++ STL

#include <iostream> 
#include <queue> 
using namespace std; 

int main () 
{   
    //  MAX HEAP DECLARATION
    priority_queue <int> MA; 
    
    // Add elements to the MAx Heap
    // in any order
    MA.push(15); 
    MA.push(46); 
    MA.push(23); 
    MA.push(9); 
    MA.push(2);

    // Print element at top of the heap 
    // every time and remove it until the 
    // heap is not empty
    cout<<"Element at top of MAx Heap at every step:\n";
    while(!MA.empty())
    {   
        // Print Top Element
        cout<<MA.top()<<" ";
        
        // Remove Top Element
        MA.pop();
    }
    
    // MIN HEAP 
    priority_queue <int, vector<int>, greater<int> > MI; 
    
    // Add elements to the MIn Heap
    // in any order
    MI.push(15); 
    MI.push(46); 
    MI.push(20); 
    MI.push(9); 
    MI.push(2); 
    
    // Print element at top of the heap 
    // every time and remove it until the 
    // heap is not empty
    cout<<"\n\nElement at top of MIn Heap at every step:\n";
    while(!MI.empty())
    {   
        // Print Top Element
        cout<<MI.top()<<" ";
        
        // Remove Top Element
        MI.pop();
    }

    return 0; 
} 
Output:
Element at top of Max Heap at every step:
46 23 15 9 2

Element at top of Min Heap at every step:
2 9 15 23 46



Heaps in Java


Java also provides us with a built-in class named PriorityQueue which can be used to implement both Max heap and Min heap easily and efficiently.

By default, the PriorityQueue class implements a Min-Heap. However, it can also be modified by using a comparator function to implement Max-Heap as well as shown in the below syntax.

Syntax:
  • Implementing Max Heap:
    Queue<Integer> max_heap = new PriorityQueue<>(                         
    Collections.reverseOrder());

  • Implementing Min Heap:
    Queue<Integer> min_heap = new PriorityQueue<>(); 

Some useful method of PriorityQueue class in Java:
  • boolean add(E element): This method inserts the specified element into this priority queue.
  • public remove(): This method removes a single instance of the specified element from this queue, if it is present.
  • public poll(): This method retrieves and removes the head of this queue, or returns null if this queue is empty.
  • public peek(): This method retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
  • void clear(): This method is used to remove all of the contents of the priority queue.
  • int size(): The method is used to return the number of elements present in the set.

Note: The above methods are applicable in case of both Max-Heap and Min-heap implementation of PriorityQueue class.

// using the PriorityQueue class 

import java.util.*;
import java.io.*;
import java.lang.*;

class GFG
{
    public static void main (String[] args) {
        
        // DECLARING MAX HEAP
        Queue<Integer> MA = new PriorityQueue<>(
                            Collections.reverseOrder());
            
        // Add elements to the Max Heap
        // in any order
            MA.push(15); 
            MA.push(46); 
            MA.push(23); 
            MA.push(9); 
            MA.push(2);
           
         // Print element at top of the heap 
        // every time and remove it until the 
        // heap is not empty
        System.out.print("Element at top of Max Heap at"
                                    + " every step:\n");
        while(!MA.isEmpty())
        { 
            // Print Top Element
            System.out.print(MA.peek()+" ");
            
            // Remove Top Element
            MA.poll();
        }
        
        // DECLARING MIN HEAP
        Queue<Integer> MI = new PriorityQueue<>(); 
          
        // Add elements to the MIn Heap
        // in any order
        MI.push(15); 
        MI.push(46); 
        MI.push(20); 
        MI.push(9); 
        MI.push(2); 
           
        // Print element at top of the heap 
        // every time and remove it until the 
        // heap is not empty
        System.out.print("\n\nElement at top of MIn Heap " 
                                    + "at every step:\n");
        while(!MI.isEmpty())
        { 
           // Print Top Element
           System.out.print(MI.peek()+" ");
            
           // Remove Top Element
           MI.poll();
        }
    }
}
Output:
Element at top of Max Heap at every step:
46 23 15 9 2

Element at top of Min Heap at every step:
2 9 15 23 46









darkmode