What Is Priority Queue In C++ With Examples

Difference Between the Ordinary Queue and Priority Queue

Queue and priority queue in C++ share some similar properties, but they differ significantly in their functioning. The following points highlight the key differences between a queue and a priority queue in C++:

• The queue follows the FIFO order, i.e. the first in first out approach. So, the element which is inserted first will be removed first from the queue. 
• The priority queue follows the highest priority approach. So, the element with the highest priority will be removed first. 
• In the queue, the order in which the elements are inserted is not changed internally and remains the same.
• In the priority queue, the internal order of the elements is changed according to their priorities, using an internal heap structure. 

Let us understand the difference between a queue and a priority queue with the help of an example: 

Consider the following elements:

50, 100, 20, 300, 10

1. Inserting and deleting the elements in a queue

After inserting the above elements in the order 50, 100, 20, 300, 10, the queue will become:

After insertion

50->100->20->300->10

On applying the pop() operation in the queue, the order of the elements remains the same (FIFO):

After deletion

50 

100 

20 

300 

10

2. Inserting and deleting the elements in a priority queue

After inserting the above elements in the order 50, 100, 20, 300, 10, the priority queue will become:

After insertion

50->100->20->300->10

On applying the pop() operation in the priority queue, the element with the highest priority is removed first. The internal heapify method will place the highest priority element at the top:

After deletion

300

100

50

20

10

Syntax of the Priority Queue in C++

The syntax of priority_queue class in C++ is as follows:

template <class type, class Container = vector<type>, class Compare = less <typename Container::value_type> > class priority_queue;

Description of the parameters:

• Type: This is the type of data or elements stored in the priority queue.

• Container: Since the priority queue is a container adapter, it needs an underlying container for its implementation. This parameter specifies the container that is to be used for implementing the priority queue. By default, the vector is used as a standard container. 

• Compare: This is an optional parameter. It is an object that determines the internal ordering of the elements in the priority queue. It compares the elements and maintains their relative order. The less <typename> is the default value of the function object, and it returns the same result as the less-than (x < y) operator.

The constructor of the class priority_queue can be used to declare a priority queue in C++ in the following way:

// Syntax to declare a priority queue 

priority_queue<int> name_of_queue;

The above expression will create a priority queue named name_of_queue  in C++, which will store integer-type elements in it. In C++, an internal heap structure is implemented in the priority queue. By default, a max-heap is maintained in the priority queue, which means the highest priority element will be at the top of the priority queue. A min-heap can also be created by simply specifying the suitable Compare function object. 

Become a Certified UI UX Expert in Just 5 Months!

With The Best-in-class UI UX ProgramExplore Program

The following example illustrates the priority queue in C++:

#include <iostream>  

#include<queue>  

using namespace std;  

int main()  

{  

    // declare a priority queue 

    priority_queue<int> my_queue;   

    // insert elements in the priority queue 

    my_queue.push(50);   

    my_queue.push(100);   

    my_queue.push(20);  

    my_queue.push(300); 

    my_queue.push(10); 

    cout<<"The elements in the priority queue are: \n";

    // print the elements

    while(!my_queue.empty())  

    {  

        // print the element at the top

        cout << my_queue.top();  // highest priority element is at the top

        cout << "\n";  

        // pop the element at the top

        my_queue.pop();  

    } 

    cout << "\n\n"; 

    return 0;  

}  

In the above program, a priority queue my_queue is created, which stores integer elements. The elements are inserted in the order: 50, 100, 20, 300, 10. After insertion, the elements are displayed by accessing the element at the top. The element with the highest priority will be at the top (300 in this case).

Member Functions of Priority Queue 

Just like the other C++ STL containers, the priority queue also consists of some member functions that you can directly access in your code by adding the header file for the priority queue i.e., #include<queue>. These member functions are mentioned below:

• priority_queue::empty() in C++ STL
• priority_queue::size() in C++ STL
• priority_queue::top() in C++ STL 
• priority_queue::push() in C++ STL 
• priority_queue::pop() in C++ STL 
• priority_queue::swap() in C++ STL
• priority_queue::emplace() in C++ STL 

1. priority_queue::empty()

empty() member function of the priority queue is used to determine whether the priority queue is empty or not.

Syntax

priority_queue.empty()    //name of the priority queue

                               //could be anything

Parameters

The empty() function does not accept any parameter or arguments.

Return Value

This member function has a boolean return data type, which means it will return only true or false. If your priority queue is empty, it will return True otherwise you will get False as the return value from the function. 

Example 

1. Input :  my_queue = 3, 0, 2, 5

my_queue.empty();

Output : False

2. Input :  my_queue = 0

my_queue.empty();

Output : False

3. Input :  my_queue 

my_queue.empty();

Output : True

Errors and Exceptions

1. If you try to pass an argument to the empty() function, it will throw an error.
2. It will not show an exception throw guarantee.

Below is the implementation of the empty() member function of the priority queue:

#include <iostream>

#include <queue>

using namespace std;

//function to check if the priority queue is empty or not

bool example(priority_queue<int> my_queue)

{

    if (my_queue.empty()) {

        return true;

    }

    else {

        return false;

    }

} 

int main()

{

    //creating a priority queue of integer data type

    priority_queue<int> my_queue; 

    //pushing values in the priority queue

    my_queue.push(1);

    my_queue.push(2);

    my_queue.push(3);

    my_queue.push(4);                

    // priority Queue becomes 4, 3, 2, 1  

    cout<<example(my_queue);

}

Here's How to Land a Top Software Developer Job

Full Stack Developer - MERN StackExplore Program

2. priority_queue::size()

The size() member function of the priority queue is used to obtain the size of the priority queue i.e, the total number of elements that are present inside the priority queue. 

Syntax

priority_queue.size()    //name of the priority queue

                               //could be anything

Parameters

The size() function does not accept any parameter or arguments.

Return Value

The size() member function has an integer return data type. It returns a single integer that determines the total number of elements that are present inside the priority queue.

Example 

1. Input :  my_queue = 3, 0, 2, 5

my_queue.size();

Output : 4

2. Input :  my_queue = 0

my_queue.size();

Output : 1

3. Input :  my_queue 

my_queue.size();

Output : 0

Errors and Exceptions

1. If you try to pass an argument to the size() function, it will throw an error.
2. It will not show an exception throw guarantee.

Below is the implementation of the size() member function of the priority queue:

#include <iostream>

#include <queue>

using namespace std; 

//function to determine the size of the priority queue

int example(priority_queue<int> my_queue)

{

    return my_queue.size();

}  

int main()

{

    //creating a priority queue of integer data type

    priority_queue<int> my_queue; 

    //pushing values in the priority queue

    my_queue.push(1);

    my_queue.push(2);

    my_queue.push(3);

    my_queue.push(4);                

    // priority Queue becomes 4, 3, 2, 1  

    cout<<"Size of the priority queue is: " <<example(my_queue);

}

3. priority_queue::top()

The top() member function of the priority queue is used to get the element having the highest priority in the priority queue container.

Syntax

priority_queue.top()    //name of the priority queue

                              //could be anything

Parameters

The top() function does not accept any parameter or arguments.

Return Value

The top() member function has an integer return data type. It returns a single integer that determines the largest element of the priority queue container.

Example 

1. Input :  my_queue = 3, 2, 0

my_queue.top();

Output : 3

2. Input :  my_queue = 0

my_queue.top();

Output : 0

3. Input :  my_queue = 7, 7, 3, 1, 0

my_queue.top();

Output : 7

Errors and Exceptions

1. The top() function shows an undefined behavior if the priority queue container is empty.
2. It will not show an exception throw guarantee if the priority queue container is empty.

Below is the implementation of the top() member function of the priority queue:

#include <iostream>

#include <queue>

using namespace std; 

//function to find the largest element of the priority queue container

int example(priority_queue<int> my_queue)

{

    return my_queue.top();

}  

int main()

{

    //creating a priority queue of integer data type

    priority_queue<int> my_queue; 

    //pushing values in the priority queue

    my_queue.push(1);

    my_queue.push(2);

    my_queue.push(3);

    my_queue.push(4);                

    // Priority Queue becomes 4, 3, 2, 1  

cout<<"Largest element of the priority queue is: "   <<example(my_queue);

}

4. priority_queue::push()

The push() member function of the priority queue is used to insert an element in the priority queue container. When the element is added to the priority queue container, the size of the container gets increased by 1 automatically. The element is initially inserted at the last, but as the priority queue has a maximum heap internal structure by default, the elements automatically get reordered in descending order.

Syntax

priority_queue.push(element)    //name of the priority queue

                                 //could be anything

Parameters

Value: The push() member function accepts a value as its argument that has to be inserted in the priority queue container.

Return Value

This member function does not return any value.

Example 

1. Input :  my_queue

              my_queue.push(1);

              my_queue.push(2);

              my_queue.push(3);

              my_queue.push(4);

              my_queue.push(5);

              my_queue.push(6);

Output : 6, 5, 4, 3, 2, 1

2. Input :  my_queue = 7, 5, 1, 0

              my_queue.push(3);

Output : 7, 5, 3, 1, 0

3. Input :  my_queue

my_queue.push(5);

Output : 5 

Errors and Exceptions

1. The push() function throws an error if the data type of the element that is passed to the function does not match with the data type of the priority queue container.
2. If the argument does not throw an exception, the function shows no exception either.

Below is the implementation of the push() member function of the priority queue:

#include <iostream>

#include <queue>

using namespace std; 

//function to print the elements of the priority queue container

void print(priority_queue<int> my_queue)

{

    while(!my_queue.empty())

    {

        cout << ' ' << my_queue.top();

        my_queue.pop();

    }

}  

int main()

{

    //Example 1

    //creating a priority queue of integer data type

    priority_queue<int> my_queue1;

     //pushing values in the priority queue

    my_queue1.push(1);

    my_queue1.push(2);

    my_queue1.push(3);

    my_queue1.push(4);              

      // Priority Queue becomes 4, 3, 2, 1 

    cout<<"Example 1:";

    print(my_queue1);

    cout<<endl; 

    //Example 2

    //creating another priority queue of integer data type

    priority_queue<int> my_queue2;

     //pushing identical values in the priority queue

    my_queue2.push(4);

    my_queue2.push(4);

    my_queue2.push(4); 

    //Priority Queue becomes 4, 4, 4

    cout<<"Example 2:";

    print(my_queue2);

    cout<<endl;

}

Here's How to Land a Top Software Developer Job

Full Stack Developer - MERN StackExplore Program

5. priority_queue::pop()

The pop() member function of the priority queue is used to remove the top element of the priority queue container.

Syntax

name_of_priority_queue.pop()    //name of the priority queue

                               //can be anything

Parameters

The pop() function does not accept any parameters.

Return Value

This member function does not return anything.

Example 

1. Input :  my_queue = 3, 0, 2, 1

my_queue.pop();

Output : 0, 2, 1

2. Input :  my_queue = 4, 4, 4

my_queue.top();

Output : 4, 4

3. Input :  my_queue = 7, 7, 0, 1, 7

my_queue.top();

Output : 7

Errors and Exceptions

1. If you try to pass an argument to the size() function, it will throw an error.
2. If the argument does not throw an exception, the function shows no exception either.

Below is the implementation of the pop() member function of the priority queue:

#include <iostream>

#include <queue>

using namespace std; 

int main()

{

    // creating a priority queue of integer data type

    priority_queue<int> my_queue; 

    my_queue.push(0);

    //queue becomes 0

    my_queue.push(1);

    //queue becomes 1, 0

    my_queue.push(2);

    // queue becomes 2, 1, 0

    my_queue.pop();

    // queue becomes 1, 0

    my_queue.pop();

    // queue becomes 0

    // printing the elements of the priority queue container

    while (!my_queue.empty()) {

        cout << ' ' << my_queue.top();

        my_queue.pop();

    }

}

6. priority_queue::swap()

The swap() member function of the priority queue is used to swap the elements of one priority queue with the elements of another priority queue. Both the priority queues must have the same data type and size to be eligible for swapping elements. After swapping, the elements are printed in the reverse order since the element present at the top is printed first, and this order is followed further.

Syntax

priority_queue1.swap(priority_queue2) //name of both the priority

   //queues could be anything

Parameters

The swap() function accepts the second priority queue that takes part in swapping as its parameter.

Return Value

This member function does not return anything.

Example 

1. Input  : my_queue1 = {2, 4, 6, 8}

 my_queue2 = {1, 3, 5, 7}

 my_queue1.swap(mymy_queue2);

Output : my_queue1 = {7, 5, 3, 1}

            my_queue2 = {8, 6, 4, 2}

2. Input  : my_queue1 = {1, 3, 6, 9}

              my_queue2 = {1, 4, 8, 12}

              my_queue1.swap(mymy_queue2);

             Output : my_queue1 = {9, 6, 3, 1}

                            my_queue2 = {12, 8, 4, 1}

Errors and Exceptions

1. This function will throw an error if the priority queues are of different data types or have different sizes.
2. If the argument does not throw an exception, the function shows no exception either.

Below is the implementation of the swap() member function of the priority queue:

#include <iostream>

#include <queue>

using namespace std;

//function to print the elements of the first priority queue

void print_queue1(priority_queue<int> my_queue1)

{

    while(!my_queue1.empty())

    {

        cout<<" "<<my_queue1.top();

        my_queue1.pop();

    }

    cout<<endl;

}

//function to print the elements of the second priority queue

void print_queue2(priority_queue<int> my_queue2)

{

    while(!my_queue2.empty())

    {

        cout<<" "<<my_queue2.top();

       my_queue2.pop();

    }

    cout<<endl;

} 

int main()

{

    // creating the priority queue of integer data type

    priority_queue<int> my_queue1;

    my_queue1.push(2);

    my_queue1.push(4);

    my_queue1.push(6);

    my_queue1.push(8);

    // creating the priority queue of integer data type

    priority_queue<int> my_queue2;

    my_queue2.push(1);

    my_queue2.push(3);

    my_queue2.push(5);

    my_queue2.push(7);

    //printing the elements before swapping

    cout<<"Before Swapping"<<endl;

    cout<<"Priority Queue 1: ";

    print_queue1(my_queue1);

    cout<<"Priority Queue 2: ";

    print_queue2(my_queue2);

    my_queue1.swap(my_queue2);

    //printing the elements after swapping

    cout<<"After Swapping"<<endl;

    cout<<"Priority Queue 1: ";

    print_queue1(my_queue1);

    cout<<"Priority Queue 2: ";

    print_queue2(my_queue2);

}

Become a Certified UI UX Expert in Just 5 Months!

With The Best-in-class UI UX ProgramExplore Program

7. priority_queue::emplace()

The emplace() member function of the priority queue is used to add a new element to the priority queue container. This element is added at the top of the container. The elements are printed in the reverse order since the element at the top is printed first and the respective order is followed further.

The main difference between the push() function and emplace() function is that the push() function inserts a copy of an object in the queue that already exists while the emplace() function creates a new instance of the class in the container.

Syntax

priority_queue.emplace(element)       //name of the priority

   //queue could be anything

Parameters

The emplace() function accepts the element that has to be inserted in the priority queue container.

Return Value

This member function does not return anything.

Example 

1. Input :  my_queue

              my_queue.emplace(1);

              my_queue.emplace(2);

              my_queue.emplace(3);

              my_queue.emplace(4);

              my_queue.emplace(5);

              my_queue.emplace(6);

Output : 6, 5, 4, 3, 2, 1

2. Input :  my_queue = 7, 5, 1, 0

              my_queue.emplace(3);

Output : 7, 5, 3, 1, 0

3. Input :  my_queue

my_queue .emplace(5);

Output : 5

Errors and Exceptions

1. This function will throw an error if the argument has a different data type than the data type of priority queue.
2. If the argument does not throw an exception, the function shows no exception either.

Below is the implementation of the emplace() member function of the priority queue:

#include <iostream>

#include <queue>

using namespace std;

//function to print the elements of the priority queue container

void print(priority_queue<int> my_queue)

{

    while(!my_queue.empty())

    {

        cout << ' ' << my_queue.top();

        my_queue.pop();

    }

}

int main()

{

    //Example 1

    //creating a priority queue of integer data type

    priority_queue<int> my_queue1;

    //pushing values in the priority queue

    my_queue1.emplace(1);

    my_queue1.emplace(2);

    my_queue1.emplace(3);

    my_queue1.emplace(4);              

    // Priority Queue becomes 4, 3, 2, 1

    print(my_queue1);

    cout<<endl;

}

Use-Cases of a Priority Queue

The priority queue has several useful applications. Some major applications of the priority queue are discussed below:

• Prim’s Algorithm: This popular algorithm for finding a minimum spanning tree can also be implemented using the priority queue. The priority queue will be used to implement the function for extracting the nodes with the minimum key value.

• Dijkstra's shortest path algorithm: The priority queue can also be used to implement Dijkstra’s shortest path algorithm. The priority queue is used to efficiently extract the vertices with minimum distance in the graph. 

• Heap Sort: Heaps are generally used to implement the priority queue. The internal max-heap or min-heap makes the priority queue itself a max-priority-queue or a min-priority-queue, and the elements stored are removed in sorted order. 

• Data Compression: A popular data compression technique - Huffman coding can also be implemented using the priority queue. As a max-heap created for taking input in the Huffman Coding technique, a priority queue can be used to achieve this efficiently.

• A* Search algorithm: The A* Search algorithm used in AI can also be implemented using the priority queue. The priority queue is used to store the unexplored routes having the smallest lower bound.

Here's How to Land a Top Software Developer Job

Full Stack Developer - MERN StackExplore Program

How to Create a Min-Heap for the Priority Queue?

The priority queue in C++ is by default implemented using the internal max-heap structure. However, a min-heap can also be created to implement the priority queue. We will discuss two ways to create a min-heap for the priority queue in C++.

• Using greater<typename> as the Comparator Function

To create a min-heap, the priority_queue class constructor can be used along with a comparator function. By default, this comparator function is less<typename>which creates a max-heap. For a min-heap, the parameter comparator should be set to greater<typename>. 

Syntax

priority_queue <typename, vector<typename>, greater<typename>> name_of_queue;  

The following program will illustrate implementation of priority queue in C++ using a min-heap:

#include <bits/stdc++.h>

using namespace std; 

int main ()

{

    // declare a priority queue using min-heap

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

    // insert elements into priority queue

    my_queue.push(50);   

    my_queue.push(100);   

    my_queue.push(20);  

    my_queue.push(300); 

    my_queue.push(10);  

    cout<<"The elements in the priority queue are: \n";

    // print the elements

    while(!my_queue.empty())  

    {  

        // print the element at the top

    cout << my_queue.top();  // element with the highest  priority 

        cout << "\n";   

        // pop the element at the top

        my_queue.pop();  

    }  

    cout << "\n\n"; 

    return 0;  

}

In the above program, a priority queue my_queue is created which stores integer elements. The elements are inserted in the order: 50, 100, 20, 300, 10. Since it is implemented using the min-heap, the element with the highest priority will be 10 in this case.

• Using the Default Priority Queue

Another way of creating a min-heap for priority queue in C++ is by using the default priority queue based on max-heap and simply multiplying the elements to be inserted by -1. And while accessing these elements,  multiply them again with -1 to get the original values. This method for the creation of a min-heap for priority queue is generally used in competitive programming.

The following program will illustrate this approach for implementing a priority queue using the min-heap:

#include <iostream>

#include <queue>

using namespace std;

int main()

{

    // declare the default priority queue

    priority_queue<int> my_queue; 

    // declare array of elements to be inserted

    int elements[] = { 50, 100, 20, 300, 10 }; 

    // insert elements into the priority queue

    // while multiplying them by -1.

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

        my_queue.push((-1) * elements[i]);

    } 

    // print the elements in the priority queue

    cout << "The elements in the min-heap priority queue are:\n";

    while (!my_queue.empty()) { 

        // multiply elements by -1

        // to get the original values

        cout << my_queue.top() * (-1) << " ";

        my_queue.pop();

    }

    cout << "\n\n";

    return 0;

}

Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

Final Thoughts!

In this article, you learned about the ins and outs of priority queues in C++. You figured out how to use priority queues in real-life, understood the differences between an ordinary queue and a priority queue, and implemented priority using the simplest possible code. Apart from this, you also saw the different member functions of a priority queue in C++ and how to implement each of them. At the end, you learned how to implement a min-heap and explored some real-life use-cases of priority queues.

You can check out our tutorial on C++ Programming for Beginners to get an overview of the c++ concepts.

Why stop here? If you want to land your foot on professional software development and learn trending technologies, check out our course on Full Stack Web Development. This will allow you to prepare for the toughest of interviews with hands-on practical examples. You will understand advanced software development concepts such as DevOps, Agility, Java, CSS, HTML, AWS, etc.

If you want to access well-curated free online courses by top instructors, you must check out the complete list of free online courses by Simplilearn. If you have any queries or suggestions for us you can mention them in the comment box, and our experts will answer them for you as soon as possible. Happy Learning!