When working with data structures in C++, one commonly used container is the priority queue. A priority queue is similar to a regular queue, but with an added twist. Instead of following a first-in-first-out (FIFO) order like a regular queue, a priority queue maintains a specific order based on the priority assigned to each element.

How Does a Priority Queue Work?

In a priority queue, elements are stored in a way that ensures the element with the highest priority is always at the front and ready to be accessed. The priority of each element is determined either by a comparison operator or a custom comparator function.

Using the std::priority_queue Class

In C++, the standard library provides the std::priority_queue class to implement priority queues. This class is part of the <queue> header and allows you to easily create and manage a priority queue.

Here’s an example of how to use the std::priority_queue class:

#include <iostream>
#include <queue>

int main() {
    // Creating a priority queue of integers
    std::priority_queue<int> pq;

    // Inserting elements into the priority queue
    pq.push(10);
    pq.push(30);
    pq.push(20);

    // Accessing the top element
    std::cout << "Top element: " << pq.top() << std::endl;

    // Removing the top element
    pq.pop();

    // Checking if the priority queue is empty
    if (pq.empty()) {
        std::cout << "Priority queue is empty!" << std::endl;
    }

    // Get the size of the priority queue
    std::cout << "Size of priority queue: " << pq.size() << std::endl;

    return 0;
}

In the example above, we first include the necessary headers <iostream> and <queue>. Then, we create a priority queue pq to store integers.

We insert elements into the priority queue using the push() method, and access the top element using top(). To remove the top element, we use pop(). The empty() method checks if the priority queue is empty, and size() returns the number of elements in the priority queue.

Customizing the Priority Queue

By default, the std::priority_queue class orders elements in descending order, using the < operator. If you need to change the order or use a custom object as an element in the priority queue, you can provide a custom comparator.

Here’s an example of using a custom comparator to order strings in ascending order:

#include <iostream>
#include <queue>
#include <functional> // for std::greater

int main() {
    // Creating a priority queue of strings in ascending order
    std::priority_queue<std::string, std::vector<std::string>, std::greater<std::string>> pq;

    // Inserting elements into the priority queue
    pq.push("orange");
    pq.push("apple");
    pq.push("banana");

    // Accessing the top element
    std::cout << "Top element: " << pq.top() << std::endl;

    // Removing the top element
    pq.pop();

    // Checking if the priority queue is empty
    if (pq.empty()) {
        std::cout << "Priority queue is empty!" << std::endl;
    }

    // Get the size of the priority queue
    std::cout << "Size of priority queue: " << pq.size() << std::endl;

    return 0;
}

In this example, we use the std::greater comparator to order the strings in ascending order. The std::greater functor is provided by the <functional> header.

Conclusion

Priority queues are a powerful data structure that can be useful in various scenarios where elements need to be accessed based on their priority. The std::priority_queue class in C++ provides a convenient way to work with priority queues and can be customized based on your specific requirements.