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:
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:
Some useful method of PriorityQueue class in Java:
Note: The above methods are applicable in case of both Max-Heap and Min-heap implementation of PriorityQueue class.
// 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 46Heaps in Java
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
No comments