Core Operations

Priority queues are specialized ordered collections where the element with highest assigned priority is always positioned at the front of the sequence. The C++ Standard Library's priority_queue container adapter supports the following core operations:

1. push(value): Inserts a new element into the queue, triggering internal reordering to maintain the correct priority sequence.
2. pop(): Deletes the front (highest-priority) element from the queue.
3. top(): Returns a read-only refeernce to the highest-priority front element with out modifying the queue's contents.
4. size(): Returns the total count of elements currently stored in the queue.
5. empty(): Returns a boolean true if the queue contains no elements, otherwise returns false.

The following example demonstrates usage of a default integer priority queue sorted in descending order:

#include <queue>
#include <iostream>

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

    sorted_pq.push(4);
    sorted_pq.push(1);
    sorted_pq.push(8);

    std::cout << "Current top element: " << sorted_pq.top() << "\n"; // Output: 8

    sorted_pq.pop();

    std::cout << "Top element after pop: " << sorted_pq.top() << "\n"; // Output: 4

    std::cout << "Queue size: " << sorted_pq.size() << "\n"; // Output: 2

    std::cout << "Queue empty status: " << (sorted_pq.empty() ? "true" : "false") << "\n"; // Output: false

    return 0;
}

Max-Heap and Min-Heap Configuration

priority_queue can be configured to emulate either a max-heap or min-heap by specifying a custom comparator template paramter.

1. Max-Heap Implementation: The std::less comparator is used to order elements in descending sequence, where the largest value is treated as the highest priority. This is the default behavier if no comparator is explicitly specified. An explicit max-heap declaration is shown below:

#include <queue>
#include <vector>

std::priority_queue<int, std::vector<int>, std::less<int>> max_heap;

2. Min-Heap Implementation: Use the std::greater comparator to order elements in ascending sequence, where the smallest value is treated as the highest priority:

#include <queue>
#include <vector>

std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

When no comparator or underlying container is specified, priority_queue defaults to using std::less with a std::vector underlying storage, resulting in a max-heap implementation.