C++ Priority Queue

In C++, the STL priority_queue provides the functionality of a priority queue data structure.

A priority queue is a special type of queue in which each element is associated with a priority value and elements are served based on their priority.

To learn more about priority queues, visit our Priority Queue Data Structure.

Create a Priority Queue

In order to create a priority queue in C++, we first need to include the queue header file.

#include <queue>

Once we import this file, we can create a priority_queue using the following syntax:

priority_queue<type> pq;

Here, type indicates the data type we want to store in the priority queue. For example,

// create a priority queue of integer type
priority_queue<int> pq_integer;

// create a priority queue of string type
priority_queue<string> pq_string;

Note: By default, STL priority_queue gives the largest element the highest priority.

C++ Priority Queue Methods

In C++, the priority_queue class provides various methods to perform different operations on a queue.

Insert Element to a Priority Queue

We use the push() method to insert an element into the priority queue. For example,

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

int main() {

  // create a queue of int
  priority_queue<int> numbers;

  // add items to priority_queue
  numbers.push(1);
  numbers.push(20);
  numbers.push(7);

  cout << "Priority Queue: ";

  // display all elements of numbers
  while(!numbers.empty()) {
    cout << numbers.top() << ", ";   
    numbers.pop();
  }

  cout << endl;

  return 0;
}

Output

Priority Queue: 20, 7, 1,

In the above example, we have created a priority_queue of integers called numbers. Here, we have used the push() method to insert the following elements into the queue: 1, 20, 7.

numbers.push(1);

Notice that we have pushed elements in random order but when printing them we get the integers sorted in descending order: 20, 7, 1.

The top of the queue is the maximum element in the queue since priority_queue is implemented as max-heap by default.

Printing Queue Elements

We cannot iterate through a priority queue like we can with vectors and other containers.

This is why we have used a while loop and various priority_queue methods to print its elements in the program above.

while(!numbers.empty()) {
  cout << numbers.top() << ", ";
  numbers.pop();
}

This is because priority_queue is an STL Container Adapter that provides restrictive access to make it behave like a standard priority queue data structure.

So, we print its top and then pop the element repeatedly inside a loop until the queue is empty.

We will see about pop(), top() and empty() in the coming sections.

Remove element from the Priority Queue

We can remove an element from the priority_queue using the pop() method. This removes the element with the highest priority.

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

// function prototype for display_priority_queue()
void display_priority_queue(priority_queue<int> pq); 

int main() {

  // create a queue of int
  priority_queue<int> numbers;

  // add items to priority_queue
  numbers.push(1);
  numbers.push(20);
  numbers.push(7);
 
  cout << "Initial Priority Queue: ";
  display_priority_queue(numbers);
  
  // remove element from queue
  numbers.pop();
  
  cout << "Final Priority Queue: ";
  display_priority_queue(numbers);

  return 0;
}

// utility function to dislay priority queue
void display_priority_queue(priority_queue<int> pq) {
  while(!pq.empty()) {
    cout << pq.top() << ", ";   
    pq.pop();
  }

  cout << endl;
}

Output

Initial Priority Queue: 20, 7, 1, 
Final Priority Queue: 7, 1, 

In the above example, we have created a priority_queue of integers called numbers. Initially, the content of the priority queue is {20, 7, 1}.

We have then used the pop() method to remove the top element:

// pop the top element
numbers.pop();

This removes the element with the highest priority: 20.

Hence, the final queue contains the elements 7 and 1. We print the final queue using the display_priority_queue() function.

Access Element from the Priority Queue

We access the top element of the priority_queue using the top() method.

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

int main() {

  // create a priority queue of int
  priority_queue<int> numbers;

  // add items to priority_queue
  numbers.push(1);
  numbers.push(20);
  numbers.push(7);

  // get the element at the top
  int top = numbers.top();
  cout << "Top element: " << top;

  return 0;
}

Output

Top element: 20

In the above example, we have inserted elements into priority_queue in the following order: 1, 20, 7.

Then, we print the top element using:

// returns 20
numbers.top();

Here, 20 has the highest priority, so it is at the top.

Get the size of the Priority Queue

We use the size() method to get the number of elements in the priority_queue.

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

int main() {

  // create a priority queue of string
  priority_queue<string> languages;

  // add items to priority_queue
  languages.push("C++");
  languages.push("Python");
  languages.push("Java");

  // get the size of queue
  int size = languages.size();
  cout << "Size of the queue: " << size;

  return 0;
}

Output

Size of the queue: 3

In the above example, we have created a priority_queue of strings called languages and added 3 elements to it.

Then we used the size() method to find the number of elements in the queue:

int size = languages.size();

Since we have added 3 elements to the queue, languages.size() returns 3.

Check if the Priority Queue is Empty

We use the empty() method to check if the priority_queue is empty. This method returns:

• 1 (true) - if the priority queue is empty
• 0 (false) - if the priority queue is not empty

Example: C++ empty() Method

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

int main() {

  // create a priority queue of ints
  priority_queue<string> languages;

  cout << "Is the queue empty? ";

  // check if the queue is empty  
  if (languages.empty()) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }

  cout << "Pushing elements..." << endl;

  // push element into the queue
  languages.push("Python");
  languages.push("C++");
  languages.push("Java");

  cout << "Is the queue empty? ";

  // check if the queue is empty
  if (languages.empty()) {
    cout << "Yes";
  }
  else {
    cout << "No";
  }

  return 0;
}

Output

Is the queue empty? No
Popping all the elements
Is the queue empty? Yes

In the above example, we have used the empty() method to determine if the languages priority queue is empty,

if (languages.empty()) {
  cout << "Yes" << endl;
}
else {
  cout << "No" << endl; 
}

Initially, the queue has no elements in it. So languages.empty() returns true.

We then inserted elements into the queue and used the empty() method again. This time, it returns false.

Min-Heap Priority Queue

We can also create a min-heap priority_queue that arranges elements in ascending order. Its syntax is:

priority_queue<type, vector<type>, greater<type>> pq; 

For example,

// integers are arranged in ascending order
priority_queue<int, vector<int>, greater<int>> pq_integers;

In this type of priority queue, the smallest element gets the highest priority.

Example: Min-Heap Priority Queue

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

int main() {

  // create a priority queue of int
  // arranges elements in ascending order
  priority_queue<int, vector<int>, greater<int>> numbers;

  // add items to priority_queue
  numbers.push(1);
  numbers.push(20);
  numbers.push(7);

  // print element with highest priority
  cout << "Top element: " << numbers.top();

  return 0;
}

Output

Top element: 1