std::priority_queue

A priority queue is a data structure that maintains a collection of elements with associated priorities.

The element with the highest priority can be efficiently retrieved and removed from the queue.

The priority queue follows the Partial Order Property, which means the elements are sorted based on their priority.

std::priority_queue Class in C++

To work with priority queues in C++, you can use the std::priority_queue class from the <queue> header. The std::priority_queue class template has the following syntax:

#include <queue>

std::priority_queue<T, Container, Compare> myPriorityQueue;

Here, T is the type of elements to be stored in the priority queue, Container is the underlying container that holds the elements (usually std::vector<T> or std::deque<T>), and Compare is the comparator function that defines the priority order for the elements. If Compare is not provided, the default comparator (std::less<T>) is used, which results in a max-heap.

Functions in std::priority_queue

Let’s create a std::priority_queue and explore its important functions with code examples:

push():

Inserts a new element into the priority queue.

#include <iostream>
#include <queue>

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

    myPriorityQueue.push(5);
    myPriorityQueue.push(2);
    myPriorityQueue.push(8);

    return 0;
}

pop():

Removes the element with the highest priority from the priority queue.

#include <iostream>
#include <queue>

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

    myPriorityQueue.push(5);
    myPriorityQueue.push(2);
    myPriorityQueue.push(8);

    myPriorityQueue.pop();

    return 0;
}

top():

Accesses the element with the highest priority (without removing it).

#include <iostream>
#include <queue>

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

    myPriorityQueue.push(5);
    myPriorityQueue.push(2);
    myPriorityQueue.push(8);

    std::cout << "Top element: " << myPriorityQueue.top() << std::endl;

    return 0;
}

empty():

Checks if the priority queue is empty.

#include <iostream>
#include <queue>

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

    if (myPriorityQueue.empty()) {
        std::cout << "Priority queue is empty." << std::endl;
    } else {
        std::cout << "Priority queue is not empty." << std::endl;
    }

    return 0;
}

size():

Returns the number of elements in the priority queue.

#include <iostream>
#include <queue>

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

    myPriorityQueue.push(5);
    myPriorityQueue.push(2);
    myPriorityQueue.push(8);

    std::cout << "Number of elements in the priority queue: " << myPriorityQueue.size() << std::endl;

    return 0;
}

Iterating through the priority queue:

#include <iostream>
#include <queue>

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

    myPriorityQueue.push(5);
    myPriorityQueue.push(2);
    myPriorityQueue.push(8);

    while (!myPriorityQueue.empty()) {
        std::cout << "Top element: " << myPriorityQueue.top() << std::endl;
        myPriorityQueue.pop();
    }

    return 0;
}

Time Complexity and Space Complexity

The time complexity of the essential priority_queue operations is as follows:

• push(): O(log N)
• pop(): O(log N)
• top(): O(1)
• empty(): O(1)
• size(): O(1)

Here, N is the number of elements in the priority queue.

The space complexity of a priority queue is the space required to store its elements. For a std::priority_queue, using std::vector or std::deque as the underlying container, the space complexity is O(N), where N is the number of elements in the priority queue.

Conclusion

std::priority_queue is a powerful container in C++ that implements a priority queue data structure. It allows easy management of elements based on their priorities, making it suitable for a wide range of applications such as Dijkstra’s algorithm, Huffman coding, and more. Understanding the functions and their time and space complexity helps in efficiently utilizing the std::priority_queue container in various scenarios.