Priority Queue in C++ (STL)

In this lecture, we will learn about the STL Container Priority Queue in C++ – Standard Template Library (STL).

What is a Priority Queue?

A priority queue is a type of queue that stores elements based on their priority. Unlike a standard queue, which operates on a “first in, first out” (FIFO) principle, a priority queue works on a priority basis. Elements can be inserted into the priority queue from one end. However, when you try to remove an element, the priority queue will provide the element with the highest priority. This differs from a standard queue, where the first inserted element is always removed first.

In a priority queue, if we attempt to access the top, it will show the element with the highest priority. Similarly, if you try to remove an element, it will delete the one with the highest priority. By default, it uses the “< operator” to compare the elements inside the queue. As a result, accessing or removing an element will prioritize the highest value. Internally, the priority queue uses the heap data structure to manage its elements.

By default, a priority queue uses the Max heap. Let’s clarify this with an example.

Suppose we create a priority queue of integers and insert four elements: 8, 13, 16, and 12. Internally, due to the use of the Max heap data structure, the element at the top will be of the highest priority. Since our priority queue is of integers, the “< operator” is used to compare the integers. Hence, the top of the priority queue will have the element with the highest value, which is 16 in this case.

The priority queue might appear as follows:

If you access the top element, it will return 16 due to its highest priority. Similarly, removing the top element will eliminate the number 16. After this operation, internal adjustments ensure that the next element with the highest priority moves to the top. After removing 16, the priority queue will have 13 at the top, given that it’s now the highest priority.

For further customisation, a callback function or function object can be passed during the creation of the priority queue. If you wish to use a Min heap internally or prefer the element with the lowest priority at the top, provide the “> operator” function as the comparator during the instantiation of the priority queue. This concept will become clearer with examples.

priority_queue Container in C++

In C++, the STL priority_queue class provides the functionality of Data Structure – Priority Queue (Heap). It is a Container Adapter because it uses another container internally (like vector ) to provide the functionality of Priority Queue.

To create a priority queue object in C++, we need to include the queue header file i.e.

#include <queue>

Syntax of priority_queue is as follows,

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

• The first template parameter specifies the data type, indicating the type of elements the priority queue will hold.
• The second and third template parameters are optional.
  • The second parameter dictates the internal container the priority queue will use. By default, it employs a vector to store the elements internally.
  • The third template parameter represents the function object or comparator used to compare the elements. Its default is the < operator, ensuring that, by default, it behaves as a max heap. However, you can modify this by passing the > operator if you intend to use it as a min heap.

Let’s delve into this concept further with an example.

How to create Priority Queue in C++ & Add elements?

Firstly, we’ll create a priority queue of integers. To achieve this, we’ll specify int as the template type when declaring the priority queue object i.e.

std::priority_queue<int> pQueue;

We will then insert five integer values into this priority queue: 1, 13, 12, 9, and 4. To insert elements into the priority queue, the push() function is provided. It accepts a value as an argument and inserts it into the priority queue, as demonstrated below:

pQueue.push(1);
pQueue.push(13);
pQueue.push(12);
pQueue.push(9);
pQueue.push(4);

It will add 5 elements in the priority queue.

How to Access the Top Element from the Priority Queue?

The priority queue offers a top() function which retrieves the element from the top of the queue. If the priority queue is using the “<” operator (which is the default behavior), it internally maintains a max heap. This means the top element will always be the one with the highest priority.

From our previous discussion, recall that we inserted five integer values into the priority queue and the highest value was 13. If we invoke the top() function, it will yield the value with the maximum priority from the priority queue.

std::cout<< "Element with highest priority: "
            << maxValue 
            << std::endl;

Output:

13

The top() function returned 13, because that is the element with the highest priority in priority queue.

To remove an element from the priority queue, use the pop() function. This function doesn’t return the top element; instead, it simply removes it. With the default behavior (max heap), this means the element with the highest priority gets removed. If we were to call the pop() function on our example queue, it would remove the highest priority element, which is 13.

// Remove elements with highest priority
pQueue.pop();

It will remove 13 from the priority queue.

Subsequently, the next highest priority element would shift to the top. In our case, assuming the next highest value is 12, it would become the top element after the removal.

// Fetch the element with highest priority
maxValue = pQueue.top();

std::cout<< "Element with highest priority: "
            << maxValue 
            << std::endl;

Output:

12

It returned 12, because thats the element with highest priority now in the queue.

The complete example till now is as follows,

#include <iostream>
#include <queue>

int main()
{
    std::priority_queue<int> pQueue;

    pQueue.push(1);
    pQueue.push(13);
    pQueue.push(12);
    pQueue.push(9);
    pQueue.push(4);

    int maxValue = pQueue.top();

    std::cout<< "Element with highest priority: "
             << maxValue 
             << std::endl;

    // Remove elements with highest priority
    pQueue.pop();

    // Fetch the element with highest priority
    maxValue = pQueue.top();

    std::cout<< "Element with highest priority: "
             << maxValue 
             << std::endl;

    return 0;
}

Output:

Element with highest priority: 13
Element with highest priority: 12

How to get the number of elements in Priority Queue?

To determine the number of elements in a priority queue, the structure provides a size() function. Let’s consider an example: if we create a priority queue and add five items to it, calling the size() function should correctly return a count of five. Let’s see complete example,

#include <iostream>
#include <queue>

int main()
{
    std::priority_queue<int> pQueue;

    pQueue.push(1);
    pQueue.push(13);
    pQueue.push(12);
    pQueue.push(9);
    pQueue.push(4);

    size_t len = pQueue.size();

    std::cout<< "Number of elements in Priority Queue: "
             << len 
             << std::endl;

    return 0;
}

Output:

5

How to check if Priority Queue is empty?

Before using the top() or pop() functions, it’s crucial to ensure that the priority queue isn’t empty. Invoking these functions on an empty priority queue can lead to undefined behavior. So, how can we verify whether the priority queue has elements or not?

One might think of fetching the size and comparing it to zero, but this isn’t the most efficient approach. Instead, the priority queue provides an empty() function. When invoked, this function returns true if the priority queue is void of elements and false otherwise. For instance, if we initialize an empty priority queue without adding any elements and subsequently call the empty() function, the result would indeed be true. Let’s see an example,

#include <iostream>
#include <queue>

int main()
{
    std::priority_queue<int> pQueue;

    if(pQueue.empty())
    {
        std::cout<< "Queue is Empty " << std::endl;
    }

    return 0;
}

Output:

Queue is Empty 

How to Iterate over all elements in Priority Queue?

In C++, a priority queue doesn’t offer direct iterators like other containers (e.g., std::vector or std::list). However, if you wish to iterate through its elements in order, you can do so by continuously accessing the top element and then popping it off the queue. This method will process all the elements based on their priority, but remember that by the end, the priority queue will be empty.

#include <iostream>
#include <queue>

int main()
{
    std::priority_queue<int> pQueue;

    pQueue.push(1);
    pQueue.push(13);
    pQueue.push(12);
    pQueue.push(9);
    pQueue.push(4);

    // Iterating and emptying the priority queue.
    while (!pQueue.empty())
    {
        // Access and display the top element.
        std::cout << pQueue.top() << " ";

        // Remove the accessed element.
        pQueue.pop();
    }

    return 0;
}

Output:

13 12 9 4 1

How to Customise the Priority Queue in C++

It’s paramount to understand that the priority queue, by default, keeps the element with the highest priority at the top. This behavior arises because it employs the “less than” operator to compare elements. If you wish to customize this behavior, adjustments can be made during the instantiation of the priority queue.

In C++, the default behavior of a priority queue uses the less operator for element comparison. As a result, it functions as a max-priority queue by default. This means the element at the top will be the one with the highest priority. If you desire to invert this behavior, preferring the lowest priority element (e.g., the smallest value) at the top, you can pass a different function object when creating the priority queue.

For instance, to achieve a min-priority queue, you can utilize the greater function for element comparison:

#include <iostream>
#include <queue>

int main()
{
    std::priority_queue<int,
                        std::vector<int>,
                        std::greater<int>>
                                        pQueue;
    pQueue.push(6);
    pQueue.push(13);
    pQueue.push(12);
    pQueue.push(2);
    pQueue.push(11);

    int elem = pQueue.top();

    std::cout<< "Element with highest priority: "
             << elem 
             << std::endl;

    return 0;
}

Output:

Element with highest priority: 2

Now, the top element will be ‘2’, the smallest number, because we used the std::greater<int> function as comprator while creating priority_queue object. Therefore it is using Min Heap internally.

Upon removing the top element, ‘1’, the next smallest element, ‘6’, will rise to the top.

How to use Priority Queue with User defined class in C++?

There are times when you might want to store user-defined objects in the priority queue. Consider an example where you want to store student objects. A student might have several attributes like name, marks, and city. However, suppose you only want to use the marks attribute to determine priority.

To achieve this, you can overload the < operator within the student class:

#include <iostream>
#include <queue>
#include <string>

class Student {
public:
    std::string name;
    int marks;
    std::string city;

    // Constructor for ease of creation
    Student(std::string n, int m, std::string c) 
    : name(n), marks(m), city(c) {}

    bool operator<(const Student &other) const {
        return this->marks < other.marks;
    }
};

int main() {
    std::priority_queue<Student> pq;

    // Let's create some student objects 
    // and add them to the priority queue
    pq.push(Student("Priya", 89, "Mumbai"));
    pq.push(Student("Sanjay", 98, "Delhi"));
    pq.push(Student("Anil", 94, "Bangalore"));
    pq.push(Student("Rita", 75, "Kolkata"));

    // Now, let's see which student has the highest marks:
    Student topStudent = pq.top();

    std::cout << "Student with highest marks:" << std::endl;
    std::cout << "Name: " << topStudent.name << std::endl;
    std::cout << "Marks: " << topStudent.marks << std::endl;
    std::cout << "City: " << topStudent.city << std::endl;

    // If you pop from the queue and check again, 
    // you'd get the next student with the highest marks.
    pq.pop();

    Student secondTopStudent = pq.top();

    std::cout << "\nStudent with second highest marks:" << std::endl;
    std::cout << "Name: " << secondTopStudent.name << std::endl;
    std::cout << "Marks: " << secondTopStudent.marks << std::endl;
    std::cout << "City: " << secondTopStudent.city << std::endl;

    return 0;
}

Output:

Student with highest marks:
Name: Sanjay
Marks: 98
City: Delhi

Student with second highest marks:
Name: Anil
Marks: 94
City: Bangalore

When executed, this code should first display the student with the highest marks (Sanjay) and then the student with the second highest marks (Anil). This illustrates how a user-defined type like the Student class can work within the confines of the C++ priority queue, with the order being dictated by an attribute (in this case, marks).

Summary

So, today we learned about Priority Queue. In C++, a priority queue is a container adapter that provides constant-time access to the largest (or smallest) element, with logarithmic time insertion and extraction. It uses a comparison function, defaulting to std::less (max heap), but can be customized. The underlying data structure is typically a binary heap, often implemented using a vector.