skip to content

In C++, why does std::priority_queue<int> pop the largest element first, and how do you get a min-heap or a custom task order?

level: middleimportance: must knowfreq 65%

answer

  1. the comparator means comes out later
  2. std::less builds a max-heap
  3. std::greater needs the container too
  4. top() is const, pop() is void

basics

~10 s

std::priority_queue keeps a heap under its comparator, default std::less, so the greatest element is on top. Use std::greater<T> for a min-heap, or a comparator returning true when a should come out after b.

solid answer

~40 s

`std::priority_queue<T, Container = std::vector<T>, Compare = std::less<typename Container::value_type>>` is an adaptor that keeps its container arranged as a heap with the standard heap algorithms. With `std::less`, the element that no other element exceeds sits at the front, so `top()` is the largest. Read the comparator as "a comes out after b": `std::greater<int>` flips that and gives a min-heap, but because `Compare` is the third template argument you must spell the container as well: `std::priority_queue<int, std::vector<int>, std::greater<int>>`. For tasks, write a comparator such as `a.priority < b.priority` to serve high priorities first. `push` and `pop` cost O(log n); `top()` returns a `const_reference`, so you cannot move a `std::unique_ptr` out of it; `pop()` returns `void`; and elements with equal priority come out in no guaranteed order, so add a sequence number when FIFO matters.

code

cpp · 30 lines
cpp
#include <cstdio>
#include <functional>
#include <queue>
#include <string>
#include <vector>

struct Task { int priority; std::string name; };

// Returns true when a should be served AFTER b: the queue keeps the
// element that compares "largest" on top.
struct ByPriority {
    bool operator()(const Task& a, const Task& b) const { return a.priority < b.priority; }
};

int main() {
    std::priority_queue<int> maxFirst;                                   // std::less: max-heap
    std::priority_queue<int, std::vector<int>, std::greater<int>> minFirst;
    for (int x : {5, 1, 9, 3}) { maxFirst.push(x); minFirst.push(x); }
    std::printf("max-heap top=%d, min-heap top=%d\n", maxFirst.top(), minFirst.top());

    std::priority_queue<Task, std::vector<Task>, ByPriority> scheduler;
    scheduler.push({2, "flush logs"});
    scheduler.push({9, "render frame"});
    scheduler.push({5, "save game"});
    while (!scheduler.empty()) {
        const Task& next = scheduler.top();      // const_reference
        std::printf("%d %s\n", next.priority, next.name.c_str());
        scheduler.pop();                         // returns void
    }
}

go deeper

for a junior

Know that std::priority_queue gives the largest element first by default and that std::greater<T> turns it into a min-heap.

for a middle

Explain the template parameters, read the comparator as comes out after, write a custom task comparator, and state push and pop at O(log n).

for a senior

Handle the sharp edges: const top() blocking moves of move-only types, unstable ordering among equals, no decrease-key, and lazy deletion of stale entries.

for a principal

Decide when a heap-based scheduler is enough and when you need ordered containers or a timing wheel for cancellation, reprioritization and fairness among equal priorities.

## The declaration explains the default The standard declares the adaptor as: ```cpp template<class T, class Container = vector<T>, class Compare = less<typename Container::value_type>> class priority_queue; ``` It holds a protected container `c` and a comparator `comp`, and implements every operation with the heap algorithms on `c`: `push` is `push_back` followed by `push_heap`, `pop` is `pop_heap` followed by `pop_back`, and `top()` returns `c.front()`. The heap algorithms keep the element that is greatest under `comp` at the front. With the default `std::less<int>`, "greatest" means the largest int, so `std::priority_queue<int>` is a **max-heap**. The container must have random-access iterators and support `front()`, `push_back()` and `pop_back()`; the standard names `std::vector` and `std::deque` as usable. ## Reading the comparator correctly The comparator is a strict weak ordering, and the most reliable way to read it is: **`comp(a, b)` returns true when `a` should come out after `b`**. - `std::less<int>`: `a < b` means the smaller one comes out later, so the largest comes out first. - `std::greater<int>`: `a > b` means the larger one comes out later, so the **smallest** comes out first: a min-heap. - A task scheduler serving high priorities first uses `a.priority < b.priority`. Because `Compare` is the **third** template argument, a min-heap must name the container too: ```cpp std::priority_queue<int, std::vector<int>, std::greater<int>> soonest; ``` A lambda comparator works with `decltype`. Before C++20 a lambda's closure type had no default constructor, so you also had to pass the lambda to the constructor; with libc++, `std::priority_queue<int, std::vector<int>, decltype(later)> q;` fails under C++17 with "no matching constructor for initialization of 'value_compare'" and compiles under C++20, where captureless lambdas are default-constructible. ## The interface is deliberately small - **`top()` returns `const_reference`.** You can read the highest-priority element but not modify it, because changing it would break the heap. It also means `std::move(q.top())` yields a const rvalue, so a move-only element cannot be moved out: in a libc++ test with `std::priority_queue<std::unique_ptr<int>> q`, the line `auto p = std::move(q.top());` fails with "call to implicitly-deleted copy constructor of 'std::unique_ptr<int>'". - **`pop()` returns `void`**: read `top()` first, then `pop()`. - **No iteration, no erase of an arbitrary element, no decrease-key.** If a task's priority changes, the usual pattern is to push a new entry and skip stale ones when they reach the top. - **Equal priorities come out in no guaranteed order.** The heap algorithms are not stable; in a libc++ run, eight equal-priority tasks pushed in order 0 to 7 came out as 0 1 3 7 6 5 4 2. Add an increasing sequence number and compare it second when FIFO among equals matters. ## Choosing and pre-sizing the container - `std::vector` is the default and the usual choice: contiguous, with cheap `push_back` and `pop_back`. - `std::deque` is allowed and avoids reallocating elements, at the cost of slower indexing inside the heap algorithms. - To avoid reallocations while a scheduler warms up, build the queue from a vector whose capacity is already reserved: `std::vector<Task> buf; buf.reserve(1024);` then `std::priority_queue<Task, std::vector<Task>, ByPriority> q(ByPriority{}, std::move(buf));`. The constructor taking a comparator and a `Container&&` adopts that buffer, and an empty buffer is trivially a valid heap. ## Costs | Operation | Complexity (from the heap algorithms) | |---|---| | `top()` | constant | | `push` / `emplace` | at most log N comparisons, plus the container's `push_back` | | `pop` | at most 2 log N comparisons | | construct from a range | at most 3N comparisons (`make_heap`) | Building the queue from a whole range at once is linear, which beats N separate pushes. ## The scheduler example A game's job system queues tasks with priorities: "render frame" at 9, "save game" at 5, "flush logs" at 2. With the comparator `a.priority < b.priority`, `top()` yields render, then save, then flush. Interview answers that get this right usually say the comparator sentence out loud, because the default "less means max-heap" surprises people used to sorting, where `std::less` means ascending order. ## Common mistakes 1. Writing `std::priority_queue<int, std::greater<int>>`, which passes the comparator as the container and does not compile; libc++ reports "no type named 'value_type' in 'std::greater<int>'". 2. Expecting `std::less` to give smallest-first because `std::sort` with `std::less` sorts ascending. 3. Holding a reference from `top()` across a `pop()`, after which it refers to a destroyed element.

  • Why can you not move a std::unique_ptr out of std::priority_queue::top()?
    `top()` returns a `const_reference`, because modifying the top element could break the heap order. `std::move` on a const lvalue produces a const rvalue, which cannot bind to the move constructor's `unique_ptr&&` parameter, so overload resolution picks the deleted copy constructor and compilation fails. Store something cheap to copy, such as an index or a `shared_ptr`, or keep the objects elsewhere.
  • How do you make tasks of equal priority come out of a std::priority_queue in arrival order?
    Give each task an increasing sequence number when it is pushed and compare it second: the comparator returns true when `a` has lower priority, or equal priority and a larger sequence number. The heap algorithms are not stable, so without a tie-breaker equal elements come out in an unspecified order.

  • std::priority_queue<int> pops the smallest element first by default
  • std::priority_queue<int, std::greater<int>> declares a min-heap
  • pop() returns the removed element
  • Tasks with equal priority come out in insertion order
  • You can iterate over a std::priority_queue to list pending tasks

Assumes C++20 or later for default-constructing a lambda comparator from decltype; under C++17 the lambda must also be passed to the constructor.