Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Priority Queue using C++ STL
3.
Operations on Priority Queue
3.1.
push()
3.2.
top()
3.3.
pop()
4.
Other Important Functions
5.
Frequently Asked Questions
5.1.
What is the Difference Between push and emplace?
5.2.
Which data structure does a priority queue utilize?
5.3.
What is the insertion complexity for an element in the priority queue using a heap?
6.
Conclusion
6.1.
Some Important Practice Problems on Priority Queue
Last Updated: Mar 27, 2024
Easy

Priority Queue using C++

Author Saksham Gupta
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up
Heap and Priority Queue

Introduction

Priority Queue is quite similar to the data structure you are already familiar with, YES Queues. A priority queue is also a queue, but the magical thing here is that a priority queue keeps track of the most important item or the item with the highest priority.

Now just like a bag, you can add elements to the priority queue. However, the only element that can be accessed or removed is the one with the highest priority. 

Priority Queue

Okay, but what priority are we talking about? In most cases, the value of the element itself is considered for assigning the priority, i.e., its magnitude.

For example, The element whose magnitude is highest is considered to be the element with the highest priority. However, in other cases, we can also mark an element with the lowest value as the element with the highest priority.

Priorities can also be set by our needs. Thus we can classify them into two categories:

  1. Min Priority Queue: Minimum element has the highest priority.
  2. Max Priority Queue: Maximum element has the highest priority.
     

Now, this sounds very interesting, but you must be thinking about how to implement it. The answer is a heap data structure. Heaps? What are they?

A heap is a data structure based on trees where the root of the tree contains the element with the highest or the lowest priority. A heap is a complete binary tree, Another new word? Well, In a complete binary tree, every node has two child nodes except the leaf nodes. This means all the leaf nodes should be at the same level, and all other internal nodes should contain two child nodes each.

Complete Binary Tree

 

In the first image, all levels are filled, and each node except the leaf node has two children, whereas if we look at the second image we can see there are some nodes that don't have two children (Node with value 3).

 

Now let’s see how we can use the priority queue using c++ (STL)

Also Read, Prefix Sum Array

Priority Queue using C++ STL

By default, a max priority queue is created in C++.

Syntax of Max Priority Queue

priority_queue<int> pq;

 

The syntax for Min Priority Queue

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

Here, greater<int> is a functional object which is used for performing comparisons.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Operations on Priority Queue

Let us see first how to insert elements in a priority queue.

To insert an element, we have a push() function. Let's see how it works.

push()

#include<iostream>

// Header-file for queue.
#include<queue>
       
using namespace std;
 
int main()
{
    priority_queue<int> p1;
    // Status of p1: empty.

    // Inserting elements in a queue.
    p1.push(35);
    p1.push(40);
    p1.push(95);

  // Status of p1: 95 40 35
}

 

Time Complexity of push() : O(logN), where ‘N’ is the size of the priority queue.
 

Okay, now you know how to insert an element in the priority queue but how to access the topmost element?

We can do that easily by the top() function provided in STL. Let’s understand it better using the following example.

top()

#include<iostream>

// Header-file for queue.
#include<queue>      

using namespace std;

int main(){
  priority_queue<int> p1;
  p1.push(35); 
  p1.push(95);
  p1.push(89);
  p1.push(21);

  // Fetching element of highest priority, i.e., 95.
  cout << p1.top();   
}

 

Output

95

 

 

Time Complexity of top()O(1)
 

What if I have to delete the topmost element?

To achieve that, we can use the pop() function, as shown below:

pop()

#include<iostream>

// Header-file for queue.
#include<queue>      
   
using namespace std;

void print(priority_queue<int> pq) {


      // Print priority queue.
      while(pq.size()!=0)
      {
        cout<<pq.top()<<" ";
        pq.pop();
      }

      cout<<endl;
}


 

int main(){
    priority_queue<int> p1;  
    p1.push(35); 
    p1.push(40);
    p1.push(95);
    p1.push(20);

    // Printing status of priority queue.
    print(pq);

    // Deleting the top element.
    p1.pop();  

    

    // Printing status of priority queue.
    print(pq);     

}

 

Output:

95 40 35 20

40 35 20

 

Time Complexity of pop(): O(logN), where ‘N’ is the size of the priority queue.

Other Important Functions

By now, you have understood the basic functions of the priority queue using c++. Now let’s look at other functions that STL provides us.

  1. empty() – It checks if the queue is empty or not. If the queue is empty, it returns true, otherwise false. It does not take any parameters. 
priority_queue<int> pq;


if (pq.empty()) {
  cout<<"Queue is Empty";
}
else {
    cout<<"Queue is not empty";
}

      Time Complexity of empty() : O(1)

2. size() – This function returns the number of elements present in the priority queue. It does not take any parameters.

priority_queue<int> pq;
pq.push(10);
pq.push(20);
cout<<"Size of Priority Queue"<<" "<< pq.size();

      Output

Size of Priority Queue 2

    Time Complexity of size() : O(1)

3. swap() –   It is used to exchange the contents of two priority queues but the queues must be of the same type, although sizes may differ. It takes one parameter, i.e., the priority queue whose values need to be swapped.        

void print(priority_queue<int> pq) {

      // Print priority queue.
      while(pq.size()!=0)
      {
        cout<<pq.top()<<" ";
        pq.pop();
      }
      cout<<endl;
} 

int main(){
      priority_queue<int> pq1; 
      priority_queue<int> pq2;

      pq1 = {1, 2, 3, 4};
      pq2 = {3, 5, 7};
      // Before Swapping.
      print(pq1);
      print(pq2);

      pq1.swap(pq2);

      //After Swapping.
      print(pq1);
      print(pq2);

}

      Output    

1 2 3 4

3 5 7

3 5 7

1 2 3 4

      Time Complexity of swap() : O(N), where ‘N’ is the number of elements.

4. priority_queue :: value_type:  This method represents the type of object that is stored in our priority queue. It acts as a synonym for the template parameter.

priority_queue<int>::value_type IntNewName;
priority_queue<int>q1;
IntNewName = 20;
q1.push(IntNewName);
IntNewName = 30;
q1.push(IntNewName);
cout << q1.top();

          Output

30

 

5. emplace() – The emplace() function adds a new element in a container at the top of the priority queue. It takes the value that needs to be added as a parameter.

priority_queue<int>pq;
pq.push(2)
cout<<pq.top()<<endl;
pq.emplace(4);
while(pq.size()!=0)
{
  cout<<pq.top()<<" ";
  pq.pop();
}

        Output        

2

4 2

  Time Complexity of emplacing: O(logN), where ‘N’ is the size of the priority queue.

Frequently Asked Questions

What is the Difference Between push and emplace?

In the push() function, an object is created and then it is inserted into the priority_queue whereas, in the case of emplace(),  in-place object construction takes place which in turn saves creating an unnecessary copy.

Which data structure does a priority queue utilize?

The priority queue makes use of a heap data structure. Depending upon the requirements, it can be either a min-heap or a max-heap.

What is the insertion complexity for an element in the priority queue using a heap?

The insertion complexity for an element in the priority queue is O(logN) where N is the size of the priority queue.

Conclusion

Now, you have mastered the basics of priority queue using C++; it’s time to move ahead to Coding Ninjas Studio and practice some famous interview problems in the priority queue. Coding Ninjas Studio offers interesting interview experiences and blogs like this one. Till then, keep learning, and Happy Coding!

Some Important Practice Problems on Priority Queue

  1. Priority CPU scheduling
  2. K largest element 
  3. Running Median
  4. Matrix Median
  5. Ninja and Stops


Recommended Readings:

 

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Previous article
Priority Queue Using Doubly Linked List
Next article
Priority Queue Using a Linked List
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass