C++ STL: priority_queue (Complete Guide)

A priority queue is a type of dynamic container in STL. It stores the elements in a sorted order where the first element of the queue is the greatest of all and the other elements are sorted in non-increasing order. 

They are implemented as a heap in memory. The greatest element will be the one that will be deleted first. They are present in #include<queue> header file.

Heaps are of two types:

• Max-heap: When the elements are stored in non-increasing order and the greatest element will be the one that will be deleted first, i.e largest element has the highest priority. By default, C++ creates a max-heap.
  Syntax:
  priority_queue < data_type > name;

Example:

priority_queue < int > pq; //initializes a priority queue (max-heap) of size 0 which stores integer values 

• Min-heap: When the elements are stored in non-decreasing order and the smallest element will be the one that will be deleted first, i.e smallest element has the highest priority.
  Syntax:
  priority_queue<data_type,vector<int>,greater<int>> name;

Example:

priority_queue < int, vector < int > , greater < int >> pq; //initializes a priority queue (min-heap) of size 0 which stores integer values 

Functions on priority_queues

• push(element): It pushes the value at the end of the queue. After that, the elements are reordered according to the priority.
  Time Complexity: O(logN) where is the size of the queue
  Parameters: the element to be inserted
  Return value: void
   
• pop(): It deletes the highest priority element from the queue. If it's a min-heap, the smallest element gets deleted otherwise maximum element gets deleted. 
  Parameters: None
  Return value: void
   
• size(): It tells us the size of the queue. 
  Parameters: None
  Return value: integer, the size of the queue
   
• top(): It returns the highest priority element of the queue. 
  Parameters: None 
  Return value: the highest priority element of the queue
   
• swap(queue_name): It swaps the elements of the two queues. 
  Parameters: queue name to be swapped with
  Return value: void
   
• empty(): It tells us whether the queue is empty or not. 
  Parameters: None
  Return value: boolean, true if the queue is empty else false

Example of max-heap

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

int main() {
  priority_queue < int > pq; //max-heap
  for (int i = 0; i < 5; i++) {
    pq.push(i + 1);
  }
  cout << "The size of queue is : " << pq.size() << '\n';
  cout << "The highest priority element of queue is " << pq.top() << '\n';
  pq.pop();
  pq.pop();
  pq.push(10);
  pq.push(20);
  pq.push(30);
  if (!pq.empty()) {
    cout << "The new size of queue is " << pq.size() << '\n';
  }
  cout << "After inserting and deleting elements, the queue is " << '\n';
  while (!pq.empty()) {
    cout << pq.top() << " ";
    pq.pop();
  }
}

Output

The size of queue is : 5
The highest priority element of queue is 5
The new size of queue is 6
After inserting and deleting elements, the queue is 
30 20 10 3 2 1 

Example of min-heap

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

int main() {
  priority_queue < int, vector < int > , greater < int >> pq; //min-heap
  for (int i = 0; i < 5; i++) {
    pq.push(i + 1);
  }
  cout << "The size of queue is : " << pq.size() << '\n';
  cout << "The highest priority element of queue is " << pq.top() << '\n';
  pq.pop();
  pq.pop();
  pq.push(10);
  pq.push(20);
  pq.push(30);
  if (!pq.empty()) {
    cout << "The new size of queue is " << pq.size() << '\n';
  }
  cout << "After inserting and deleting elements, the queue is " << '\n';
  while (!pq.empty()) {
    cout << pq.top() << " ";
    pq.pop();
  }
}

Output

The size of queue is : 5
The highest priority element of queue is 1
The new size of queue is 6
After inserting and deleting elements, the queue is 
3 4 5 10 20 30