Knowledge baseExam Center
ENEnglish
Choose language13

CKTIS / C++

std::priority_queue — priority queue

std::priority_queue exposes the highest-priority element rather than the earliest inserted one. By default, the largest value is on top; std::greater<T> reverses the ordering.

Version: C++23; repository compiler flag, production runtime not attested

Syntax

#include <functional>
#include <queue>
#include <vector>

std::priority_queue<T> q;
std::priority_queue<T, std::vector<T>, std::greater<T>> min_q;

std::priority_queue from <queue> is a container adaptor maintaining a heap, not a FIFO queue. It defaults to std::vector<T> and std::less<T>, so top() identifies the largest value. The variant using std::greater<T> identifies the smallest; it requires <functional>.

push() inserts a value, while emplace() constructs an element in the container and restores the heap property. top() provides read-only access. pop() removes the top and returns void: copy any needed value before removal. Check empty() before top() and pop(); both operations require a nonempty queue.

The comparator must define a strict weak ordering. Compare(a, b) == true means that a precedes b in that ordering, giving it lower extraction priority. The adaptor exposes neither iterators nor an operation to change an arbitrary element's priority.

top() has constant cost. Heap repair during push(), emplace(), and pop() requires O(log n) comparisons. Insertion also includes the underlying container's cost: reallocation of the default std::vector<T> can make an individual insertion linear.

The example prints the same data in descending and ascending order, emptying both queues. This entry targets C++23; the linked working draft is newer and is not a frozen C++23 text.

Examples

#include <functional>
#include <iostream>
#include <queue>
#include <vector>

int main() {
    std::priority_queue<int> max_q;
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_q;

    for (int value : {4, 1, 7, 1}) {
        max_q.push(value);
        min_q.push(value);
    }

    while (!max_q.empty()) {
        std::cout << max_q.top();
        max_q.pop();
        std::cout << (max_q.empty() ? '\n' : ' ');
    }
    while (!min_q.empty()) {
        std::cout << min_q.top();
        min_q.pop();
        std::cout << (min_q.empty() ? '\n' : ' ');
    }
}

Result

7 4 1 1
1 1 4 7

The displayed code and declared result were verified in an isolated environment using the method recorded in the verification evidence for this exact version.

Sources