Priority Queue using C++

Saksham Gupta
Last Updated: May 13, 2022

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 in the priority queue. However, the only element that can be accessed or removed is the one with the highest priority. 

                                                                                                         Source: iq.opengenus

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.

 

Source: source

 

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)

Priority Queue using C++ STL.

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

Syntax of Max Priority Queue

priority_queue<int> pq;

 

Syntax for Min Priority Queue

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

 

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

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 = {1234};
      pq2 = {357};
      // 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 emplace() : O(logN) , where ‘N’ is the size of the priority queue.

 

Q) What’s the difference between push and emplace?

In 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.

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

Key Takeaways

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

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think