C++ priority queue: std::priority_queue explained

A C++ priority queue, std::priority_queue from the header <queue>, is a container that always gives you its largest element first: push() adds an element, top() reads the largest, pop() removes it. push() and pop() take logarithmic time and top() constant time. For the smallest first, give it std::greater<> as the comparison.

Four numbers in, the largest out first:

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;
    pq.push(3);
    pq.push(9);
    pq.push(4);
    pq.push(7);

    std::cout << "top: " << pq.top() << '\n';   // top: 9

    while (!pq.empty()) {
        std::cout << pq.top() << '\n';           // 9, 7, 4, 3
        pq.pop();
    }
}

It printed:

top: 9
9
7
4
3

The answer is written for C++17 (Since When’s C++17 table). The samples were built with MSVC 19.44, Clang 19.1 (MSVC STL), GCC 16.2 and Clang 23.1 (libc++), and all four printed the same unless a sentence says otherwise. A std::queue, from the same header, hands elements back in the order they arrived; a priority queue hands back the highest-ranked one, which is what a task scheduler, Dijkstra’s shortest paths or a top-k search needs.

How do you make a min-heap priority queue?

Pass std::greater<int> as the third template argument: std::priority_queue<int, std::vector<int>, std::greater<int>> hands back the smallest element first. That makes it a min-heap, a heap with the smallest element on top. The same four numbers:

std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
pq.push(3);
pq.push(9);
pq.push(4);
pq.push(7);

while (!pq.empty()) {
    std::cout << pq.top() << '\n';           // 3, 4, 7, 9
    pq.pop();
}

All four printed 3, 4, 7 and 9. The second template argument is the container the queue keeps its elements in, std::vector<int> by default; you have to write it out to reach the third. std::greater<>, without the int, works the same.

Why is the comparator backwards?

Because the comparison answers “does a come out after b?”, not “does a come first?”. std::less, the default, says yes when a is smaller, so the largest comes out first; std::greater says yes when a is larger, so the smallest does. std::sort reads the same std::less from the other end and puts the smallest first (cppreference’s std::priority_queue page: the top is the “last” element in the comparison’s order).

How do you write a priority queue comparator for a struct?

Give the queue a comparison of the field you rank by, as its third template argument. With a lambda, decltype(by_priority) names the lambda’s type, which only the compiler can spell, and the lambda itself goes to the constructor:

struct Task {
    int priority;
    std::string name;
};
// ...
auto by_priority = [](const Task& a, const Task& b) {
    return a.priority < b.priority;     // does a come out after b?
};
std::priority_queue<Task, std::vector<Task>, decltype(by_priority)>
    tasks(by_priority);

tasks.push({2, "write tests"});
tasks.push({5, "fix the crash"});
tasks.push({1, "update docs"});

while (!tasks.empty()) {
    const Task& next = tasks.top();
    std::cout << next.priority << ' ' << next.name << '\n';
    tasks.pop();
}

All four printed 5 fix the crash, 2 write tests and 1 update docs: the highest priority first. Flip the comparison to a.priority > b.priority and the lowest priority comes out first. A small function object does the same job, and the queue needs no argument to build one:

struct ByPriority {
    bool operator()(const Task& a, const Task& b) const {
        return a.priority < b.priority;
    }
};
// ...
std::priority_queue<Task, std::vector<Task>, ByPriority> queue;
queue.push({2, "write tests"});
queue.push({5, "fix the crash"});
std::cout << queue.top().name << '\n';  // fix the crash

Either way the comparison must be a strict weak ordering, a consistent “less than”: the same rule as a comparator for std::sort and std::map. The standard promises no order for elements that compare equal: with five tasks of priority 2, the three standard libraries did not all agree on the order, and none kept the push order. To keep equal priorities in the order they were pushed, add a counter to Task that rises with every push, and when two priorities are equal return a.seq > b.seq.

Under C++17, tasks.emplace(5, "fix the crash") does not compile, because Task has no constructor that takes two arguments; C++20’s parenthesized aggregate initialization makes it build. push({...}), as above, works under both.

How does std::priority_queue use a heap?

A std::priority_queue is a container adaptor, a wrapper that lets you reach only part of the container inside it, and by default that container is a std::vector kept in heap order. A heap is a binary tree stored level by level in the vector: every parent is at least as large as its children, so the largest sits at index 0, and the children of index i sit at 2i+1 and 2i+2. After 3, 9, 4 and 7 go in, the vector holds 9 7 4 3 on all three standard libraries.

The standard ([priority.queue]) defines push() as push_back() followed by std::push_heap, which sifts the new element up. It defines pop() as std::pop_heap, which swaps the top to the back and sifts the new top down, followed by pop_back(). The same algorithms, from <algorithm>, work on any vector (print writes it on one line):

std::vector<int> v{3, 9, 4, 7};

std::make_heap(v.begin(), v.end());
print(v);                               // the largest at v[0]

v.push_back(8);
std::push_heap(v.begin(), v.end());     // sift the 8 up
print(v);

std::pop_heap(v.begin(), v.end());      // the largest to the back
print(v);
v.pop_back();
print(v);

It printed:

9 7 4 3
9 8 4 3 7
8 7 4 3 9
8 7 4 3

The 8 rose to index 1 and the 7 moved down to index 4; then the old top, 9, went to the back for pop_back() to remove. All three libraries printed these layouts, but the standard promises only the heap property, not these exact positions.

To load data you already have, construct the queue from it: std::priority_queue<int> from_v(v.begin(), v.end()); runs std::make_heap once, at most 3N comparisons, instead of up to log N for each of N pushes. C++23 adds push_range() and a std::from_range constructor for the same job.

What can’t a priority queue do?

A priority queue gives you the top element and nothing else:

• pop() returns nothing (void): read top() first.
• top() and pop() on an empty queue are undefined behavior: the standard places no requirement on what the program then does. top() returns the vector’s front() and pop() ends with its pop_back(), and both are undefined on an empty vector. Check empty() first.
• No iterators and no search: there is no begin(), no find() and no member function that reaches an element below the top.
• No changing a priority: top() returns a const reference. Push a new entry and skip the old one when it reaches the top, or keep the data in a std::set, where you erase the old entry and insert the new one.

The safe loop checks empty(), reads, then pops:

std::cout << pq.size() << " waiting\n";     // 4 waiting

while (!pq.empty()) {
    int largest = pq.top();     // read it first: pop() returns void
    pq.pop();
    std::cout << largest << '\n';           // 9, 7, 4, 3
}

std::cout << pq.size() << " waiting\n";     // 0 waiting

All four printed 4 waiting, then 9, 7, 4 and 3, then 0 waiting.

priority_queue, std::set or a sorted vector?

Use a priority queue when the only question is “what comes next?”:

The other containers and adaptors are in Standard library.