C++ Priority Queue

Introduction

In this article, you will be learning about the priority queue another data structure in STL.

Similar to the stack and queues, priority queues are also a type of container adaptors, designed in a way that the first element of the queue is either the greatest or the smallest of all elements in the queue, and elements of the queue have a priority.

In C++ by default, the priority is set to the greatest first, so when we use a priority queue in C++ the first element will be the greatest element by default. We can change that to the smallest one first, we will look into that later in this article.

These priority queues are built on top of the max heap and internally use either an array or a vector as a structure. Let’s look at the methods available for the priority queue.

C++ Priority Queue

Methods of Priority Queue

• empty() – Returns true if the queue is empty otherwise returns false
• size() – Returns the size of the priority_queue i.e., the number of elements in the queue.
• top() – Returns a reference to the topmost element of the queue.
• push(i) – Adds the element ‘i’ into the queue.
• pop() – Deletes the first element of the queue.
• swap() – swaps queues of the same data types maybe with different sizes.
• emplace() – Used to insert a new element into the queue.

Now that we know different methods used on priority queues let’s look into some examples to understand this better.

Simple Implementation of Priority Queue

// CPP Program to demonstrate Priority Queue
#include <iostream>
#include <queue>
using namespace std;
  
void showpq(priority_queue<int> gq)
{
    priority_queue<int> g = gq;
    while (!g.empty()) {
        cout << '\t' << g.top();
        g.pop();
    }
    cout << '\n';
}
  
int main()
{
    priority_queue<int> gquiz;
    gquiz.push(10);
    gquiz.push(30);
    gquiz.push(20);
    gquiz.push(5);
    gquiz.push(1);
  
    cout << "The priority queue gquiz is : ";
    showpq(gquiz);
  
    cout << "\ngquiz.size() : " << gquiz.size();
    cout << "\ngquiz.top() : " << gquiz.top();
  
    cout << "\ngquiz.pop() : ";
    gquiz.pop();
    showpq(gquiz);
  
    return 0;
}

Output:

The priority queue gquiz is : 	30	20	10	5	1

gquiz.size() : 5
gquiz.top() : 30
gquiz.pop() : 	20	10	5	1

 Let us understand the above code.

So, we have first created a priority queue named gquiz.

After that, we used the push() method to insert elements into the priority_queue.

We have inserted the elements in the order 10, 30, 20, 5, and 1 and used the user-defined function showpq to print the elements of the queue.

We observe that the elements are printed in descending order that is because in C++ the priority queue makes the largest element as the first element as we have already read.

After that, we used the size() method to get the size of the queue.

We have also used the top() method to get the first element in the queue and the output is 30 as it is the greatest element in the queue, then we used the pop() method to remove the first element and then printed the elements of the queue and we can see that 30 is removed as it the first element in the queue.

Implementing a Min Heap Priority Queue

We have seen that by default C++ implements a priority queue on top of the max heap i.e., the largest element is the first element in the queue, we can also do this the other way i.e., make the first element the smallest one to implement a min-heap.

The syntax for implementing that is:

priority_queue<int , vector<int>, greater<int>> queue_name;

Let us look at an example of how to implement a min heap using a priority queue…

// C++ program to demonstrate min heap for priority queue
#include <iostream>
#include <queue>
using namespace std;
  
void showpq(
    priority_queue<int, vector<int>, greater<int> > gq)
{
    priority_queue<int, vector<int>, greater<int> > g = gq;
    while (!g.empty()) {
        cout << '\t' << g.top();
        g.pop();
    }
    cout << '\n';
}
  
int main()
{
    priority_queue<int, vector<int>, greater<int> > gquiz;
    gquiz.push(10);
    gquiz.push(30);
    gquiz.push(20);
    gquiz.push(5);
    gquiz.push(1);
  
    cout << "The priority queue gquiz is : ";
    showpq(gquiz);
  
    cout << "\ngquiz.size() : " << gquiz.size();
    cout << "\ngquiz.top() : " << gquiz.top();
  
    cout << "\ngquiz.pop() : ";
    gquiz.pop();
    showpq(gquiz);
  
    return 0;
}

Output

The priority queue gquiz is :     1    5    10    20    30

gquiz.size() : 5
gquiz.top() : 1
gquiz.pop() :     5    10    20    30

That is all for this article. Hope you got a good understanding of priority queue and how it can be used to implement min heap and max heap.

Happy Coding!