Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

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.

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:

Min Priority Queue: Minimum element has the highest priority.

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

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)

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();
}

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.

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.

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.

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.

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