C++ Priority Queue

The C++ priority queue is a container that allows you to store elements in a way that ensures the highest-priority elements are always at the front, and when you dequeue an element, you get the highest-priority one. Priority queues are often implemented using heaps, which are binary trees that satisfy the “heap property,” where the highest-priority element is at the root.

In the C++ Standard Library, you can use std::priority_queue to work with priority queues. Here’s an example of how to use it:

#include <iostream>
#include <queue>

int main() {
    // Create a max priority queue (default) - higher values have higher priority
    std::priority_queue<int> maxHeap;

    // Enqueue elements
    maxHeap.push(30);
    maxHeap.push(10);
    maxHeap.push(50);
    maxHeap.push(20);

    // Access the top (highest-priority) element
    std::cout << "Top element: " << maxHeap.top() << std::endl;

    // Dequeue elements (removes the highest-priority element)
    maxHeap.pop();

    // Check if the priority queue is empty
    if (maxHeap.empty()) {
        std::cout << "Priority queue is empty." << std::endl;
    } else {
        std::cout << "Priority queue is not empty." << std::endl;
    }

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

    return 0;
}

In this example:

• We include the <queue> header to use std::priority_queue.
• By default, std::priority_queue creates a max heap, where higher values have higher priority. If you want a min heap (lower values have higher priority), you can specify it explicitly: std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
• We use the push function to enqueue elements.
• The top function allows us to access the highest-priority (top) element without removing it.
• We use the pop function to dequeue (remove) the highest-priority element.
• empty checks whether the priority queue is empty.
• size returns the number of elements in the priority queue.

std::priority_queue is a versatile data structure and is commonly used in algorithms and applications where elements need to be processed based on their priority. You can customize it further by providing your own comparison function if needed.