Priority Queue In STL

An In-depth Look At Priority Queue In STL.

In this Explicit C++ series, we have seen stacks and queues in the previous tutorial.

In this tutorial, we will discuss yet another specialized container in STL, i.e. priority queue.

A priority queue is a container adopter in STL. A priority queue is a container having the elements arranged in non-decreasing order such that the first element is always the greatest element in the queue.

=> Visit Here For The Complete C++ Tutorials list.

Overview

In contrast to the normal queue that pushes and pops the element according to FIFO order, priority queue has elements in non-decreasing order and has a priority (fixed order) for each element

Priority queue can be viewed in a similar way as a “max heap” data structure in C++.

The general syntax of the priority queue is:

priority_queue <objectType> queue_name;

So if we want to define a priority queue of type int, we can define it as follows:

priority_queue<int> mypqueue;

Priority Queue – Operations

Let us see the operations supported by the priority queue below.

• Push: Inserts an element in the priority queue. While inserting elements, the priority of elements is maintained.
• Pop: Removes the topmost element from the priority queue.
• Top: Returns the topmost element in the priority queue i.e. greatest element in the priority queue.
• Empty: Checks if the priority queue is empty.
• Size: Returns the size of the priority queue i.e. the number of elements in the priority queue.

Let us write a program to demonstrate the usage of these functions/operations.

#include <iostream>
#include <queue>
using namespace std;
void displaypq(priority_queue <int> pri_queue)
 {
   priority_queue <int> pq = pri_queue;
   while (!pq.empty())
   {
      cout << '\t' << pq.top();
      pq.pop();
   }
   cout << '\n';
 }
int main ()
 {
   priority_queue <int> mypq;
   mypq.push(1);
   mypq.push(3);
   mypq.push(60);
   cout<<"\nPriority queue after inserting value 60: ";
   displaypq(mypq);
   mypq.push(5);
   cout<<"\n\nPriority queue after inserting value 5: ";
   displaypq(mypq);
   mypq.push(10);
   cout << "\nThe priority queue mypq is : ";
        displaypq(mypq);
   cout << "\nmypq.size() : " << mypq.size();
   cout << "\nmypq.top() : " << mypq.top();
   cout << "\nmypq.pop() : ";
   mypq.pop();
   displaypq(mypq);
   return 0;
 }

Output:

Priority queue after inserting value 60:         60             3              1

Priority queue after inserting value 5:            60             5              3              1

The priority queue mypq is :      60       10       5               3              1

mypq.size() : 5
mypq.top() : 60
mypq.pop() : 10              5             3                 1

Please check the output carefully to understand the priority queue. First, we push values 1,3,60 as shown in the first line of the output. Then we push the value 5 in the priority queue. After that, the priority queue is displayed. Note that though the value 5 is pushed after 60, the top of the priority queue is still 60.

Again we push another value 10 and still, the top of the priority queue is 60. This is because while pushing elements, the order or priority of the elements is maintained such that the greatest element is always at the top.

Conclusion

This was all about priority queue implementation in STL. In our next tutorial, we will learn more on STL containers like map and set.

=> Click Here For The Absolute C++ Training Series.