Priority queue in C++

Syntax of the C++ Priority queue

The syntax for initializing a priority queue in C++ that generates max-heap is given below:

priority_queue<datatype> name_of_priority_queue;

Example

The following example depicts how to declare a priority queue in C++ using the standard library in C++.

priority_queue<int> pq;

Since C++ generates max-heap for priority queue in C++ by default, the syntax given above is for the same. But, if we want to use a priority queue in C++, which can help to use min-heap, then we can use the following syntax:

priority_queue<datatype, vector<datatype>, greater<datatype>> name_of_priority_queue;

Example 

The following example depicts how to declare a priority queue in C++ using the standard library in C++, which can help use the min-heap of the standard library in C++.

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

Priority Queue in C++ using Standard Template Library (STL)

In C++ STL (Standard Template Library), the std::priority_queue is a container adapter that provides an efficient implementation of a priority queue. It uses a heap data structure internally to ensure that elements are always processed in order of their priority, with the highest priority element accessible through the top() function. Operations like insertion (push()), removal (pop()), and access (top()) are logarithmic in complexity, making it suitable for applications requiring efficient prioritization of elements.

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 <int, vector<int>, greater<int>> q; 

Here, greater<int> is a functional object which is used for performing comparisons.C++ Priority Queue Methods

Examples

In this section, we will learn how to use the standard library priority queue in C++.

Example of max-heap for priority queue in C++

• The code below declares a priority queue PQ that pushes four elements. 
• With the help of function showpq(), it prints the element present in PQ in the same order with which elements reside in the priority queue. 
• After that, the code shows the example of how the methods in priority queue like empty(), top(), size(), and pop() are used. 
• Since, pq is not empty so pq.empty() returns 0. 
• Size is four after pushing four elements. So, pq.size() returns 4. 
• The top element is 20. Since it is the largest element in the PQ currently. So, PQ.top() returns 20. 
• And, after using PQ.pop(), the top element 20 got removed, and we left with 10, 5, and 1.
   

Code:

// C++ Program for Priority Queue
#include <iostream>
#include <queue>
using namespace std;

void showpq(priority_queue<int> gq)
{
	priority_queue<int> p = gq;
	while (!p.empty()) {
		cout << '\t' << p.top();
		p.pop();
	}
	cout << '\n';
}

int main()
{
	priority_queue<int> pq;
	pq.push(10);
	pq.push(20);
	pq.push(5);
	pq.push(1);

	cout << "The priority queue pq is : ";
	showpq(pq);
	cout<<endl;
	cout<< "pq.empty() : "<<pq.empty()<<endl;
	cout << "pq.size() : " << pq.size()<<endl;
	cout << "pq.top() : " << pq.top()<<endl;

	cout << "After using pq.pop(), our priority queue is : ";
	pq.pop();
	showpq(pq);
	cout<<endl;

	return 0;
}

 

Output

The priority queue pq is :      20      10      5       1

pq.empty() : 0
pq.size() : 4
pq.top() : 20
After using pq.pop(), our priority queue is :   10      5       1

Example of min-heap for priority queue in C++

• The code below declares a min-heap for priority queue PQ and pushes four elements.
• With the help of function showpq it prints the element present in PQ in the same order with which components reside in the priority queue. 
• After that, the code shows the example of how the methods in priority queue like empty(), top(), size(), and pop() are used. 
• Since, pq is not empty so pq.empty() returns 0. 
• Size is four after pushing four elements. So, pq.size() returns 4. 
• The top element is 1. Since it is the smallest element in the PQ currently. So, PQ.top() returns 1. 
• And, after using PQ.pop(), the top element 1 got removed, and we left with 5, 10, and 20.
   

Code:

// C++ Program 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> > p = gq;
	while (!p.empty()) {
		cout << '\t' << p.top();
		p.pop();
	}
	cout << '\n';
}

// Driver Code
int main()
{
	priority_queue<int, vector<int>, greater<int> > pq;
	pq.push(10);
	pq.push(20);
	pq.push(5);
	pq.push(1);

	cout << "The priority queue pq is : ";
	showpq(pq);
	cout<<endl;
	cout<< "pq.empty() : "<<pq.empty()<<endl;
	cout << "pq.size() : " << pq.size()<<endl;
	cout << "pq.top() : " << pq.top()<<endl;

	cout << "After using pq.pop(), our priority queue is : ";
	pq.pop();
	showpq(pq);

	return 0;
}

 

Output

The priority queue pq is :      1       5       10      20

pq.empty() : 0
pq.size() : 4
pq.top() : 1
After using pq.pop(), our priority queue is :   5       10      20

Complexities

It is essential to know about the time and space complexity of the STL functions we will use. Let us learn about them for the priority queue in C++.

Time complexity for Priority queue 

Following are the time complexity of some functions of the priority queue.

Functions	Space Complexities
pq.push()	O(logn)
pq.pop()	O(logn)
pq.empty()	O(1)
pq.top()	O(1)

Space complexity for Priority queue

Following are the space complexity of some functions of the priority queue.

Functions	Space Complexities
pq.push()	O(1)
pq.pop()	O(1)
pq.empty()	O(1)
pq.top()	O(1)

C++ Priority queue for Structure or Class

So far, we have seen how we can use the priority queue in C++ for primitive data types. Now, we will see what happens when data types are customs, such as structure or class.

Priority Queue for structure

A structure Book having variables price and pages are shown below. 

struct Book{
	float price;
	int pages;
}

 

If we declare a priority queue with data type Book in a priority queue, it will not work. Since the structure Book consists of two variables. The priority queue will not compare two Books because of this if priority queue bpq is declared as shown below.

priority_queue<Book>bpq;

 

For solving this issue, we are going to use operator overloading. It will help the priority queue decide which structure object should be kept first.

The following code shows how a structure data type is handled in priority queue STL in c++.

Here, there is a structure book that should be ordered in the priority queue concerning the price of the Book. So, the ComparePrice function made it easy. 

 

Code:

// Program to use priority_queue STL with structure in c++

#include <iostream>
#include <queue>
using namespace std;

struct Book {

	float price;
	int pages;

	//For initializing variables of the structure
	Book(float price, int pages)
		: price(price), pages(pages)
	{
	}
};

// This is a structure for implementing the operator overloading
struct ComparePrice {
	bool operator()(Book const& b1, Book const& b2)
	{
		// return "true" if "b1" is ordered
		// before "b2", for example:
		return b1.price < b2.price;
	}
};

int main()
{
	priority_queue<Book, vector<Book>, ComparePrice> Pq;

	// While using priority_queue with structure
	// we need this kind of syntax where
	// ComparePrice is the comparison function
	int ROW= 5;
	int COL= 2;
	float arr[ROW][COL] = { { 300.6, 200 }, { 425.3, 500 },
					{ 200.4, 260 }, { 333.0, 600 }, { 523.7, 560 } };

	for (int i = 0; i < ROW; ++i) {

		Pq.push(Book(arr[i][0], arr[i][1]));

		// Pushing an object in priority_queue by using
		// the Book structure constructor
	}

	while (!Pq.empty()) {
		Book b = Pq.top();
		Pq.pop();
		cout << b.price << " " << b.pages << "\n";
	}
	return 0;
}

 

Output:

523.7 560
425.3 500
333 600
300.6 200
200.4 260

Priority queue in C++ for class

The following code shows how a class data type is handled in the STL priority queue in C++.

Here, there is a class Book that should be ordered in the priority queue in C++ concerning the price of the Book. So, the ComparePrice function made it easy. 

 

Code:

// Program in c++ to use priority_queue with class

#include <iostream>
#include <queue>
using namespace std;

class Book {
    public:
	float price;
	int pages;

	// This will used to initialize the variables
	// of the class
	
	Book(float price, int pages)
		: price(price), pages(pages)
	{
	}
};


// Operator overloading is implemented here
bool operator<(const Book & b1, const Book & b2)
{
	// This will return true when second book
    // has greater price. Suppose we have b1.price=500.5
    // and p2.height=550.5 then the object which
    // have max price will be at the top(or
    // max priority)
	return b1.price < b2.price;
}

int main()
{
	priority_queue<Book> Pq;

	// When we use priority_queue with class
	// then we need this kind of syntax where
	// ComparePrice is the functor or comparison function
	int ROW= 5;
	int COL= 2;
	float arr[ROW][COL] = { { 300.6, 200 }, { 425.3, 500 },
					{ 200.4, 260 }, { 333.0, 600 }, { 523.7, 560 } };

	for (int i = 0; i < ROW; ++i) {

		Pq.push(Book(arr[i][0], arr[i][1]));

		// Insert an object in priority_queue by using
		// the Book class constructor
	}

	while (!Pq.empty()) {
		Book b = Pq.top();
		Pq.pop();
		cout << b.price << " " << b.pages << "\n";
	}
	return 0;
}

 

Output:

523.7 560
425.3 500
333 600
300.6 200
200.4 260

C++ Priority Queue Methods

In this section, we will learn about the methods present in the STL priority queue in C++.

Method	Use
top()	It returns the reference to the top element in the priority queue.
push()	It helps to insert the element at the end of the priority queue.
pop()	It helps to delete or remove the first element of the priority queue.
size()	This return the current size of priority queue.
empty()	It returns 0 or 1. 1 if the priority queue is empty and 0 if it is not empty.
emplace()	It helps insert a new element in the priority queue.
swap()	It helps to swap the values present between two priority queues having the same data types.

Operations on Priority Queue in C++

1. Insert Element to a Priority Queue

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

Example: 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
}

 
Output

95 40 35

 

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

2. Access the Top Element of the Priority Queue

We can access the top element of the priority queue easily by the top() function provided in STL. Let’s understand it better using the following example.

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)

3. Delete the topmost element

What if I have to delete the topmost element?

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

Example: 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.

4. Check whether the Priority Queue is Empty or Not

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. 

Example:empty()

priority_queue<int> pq;

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

Time Complexity of empty() : O(1)

5. Check the Size of the Priority Queue

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

Example:size()

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)

6. Swap Contents of a Priority Queue

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.    

Example:swap()    

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.

7. Value Type Representation in a Priority Queue

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.

Example:priority_queue :: value_type

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

 

You can also try this code with Online C++ Compiler

Run Code

Output

30

8. Emplace a new element into the priority queue container

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

 

You can also try this code with Online C++ Compiler

Run Code

Output        

2
4 2 

 

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

Difference Between Priority Queue and Queue

Feature	Queue	Priority Queue
Definition	A queue is a data structure that follows the FIFO (First In First Out) principle.	A priority queue is a data structure that stores elements based on their priority.
Order of Processing	Elements are processed in the order they arrive.	Elements are processed based on priority, not arrival order.
Insertion	New elements are added at the back of the queue.	New elements can be inserted at any position based on their priority.
Removal	The element removed is always the one at the front.	The element removed is the one with the highest priority.
Use Cases	Useful for scheduling tasks in the order they are received, such as print jobs.	Useful for scenarios where certain tasks need to be prioritized, such as job scheduling in operating systems.
Complexity	Typically O(1) for insertion and O(1) for removal.	Insertion can be O(log n) and removal can also be O(log n) depending on the implementation.
Implementation	Usually implemented using arrays or linked lists.	Often implemented using heaps or binary trees.

Frequently Asked Questions

Can the priority queue in C++ store duplicate elements?

Yes, the priority queue standard library in C++ allows duplicate elements.

How does the priority queue in C++ sort the elements?

The priority queue returns the largest element while popping in the general case. So, each time it gives the largest element, sorting happens.

Is priority queue in C++ stable?

No, std::priority_queue in C++ is not stable. It does not preserve the order of elements with equal priority during insertion or removal.

State two applications of the priority queue in C++.

Prim's algorithm and Dijkstra's shortest path algorithm are two applications of the priority queue.

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

In this article, we learned the concept of priority queues in C++. We began by understanding the fundamental principles behind priority queues and their differences from standard queues. We examined various implementations, including how to use the C++ Standard Library's priority queue functionality effectively.

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:

• Doubly Linked List
• Heap and Priority Queue
• STL in C++
• Priority Queue Using Array in C++
• Applications of Priority Queue
• Priority Queue in Java

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.