std::priority_queue & the Heap Algorithms

August 2026 · 20 min read

Parts 1–4 built a heap from scratch so the machinery is not a black box. In production you will almost always use the standard library instead. This post maps everything we built onto what C++ ships, and settles the comparator convention that trips up nearly everyone the first time.

For an exhaustive tour of the STL surface — custom comparators over structs, lambdas, pairs, and the full algorithm family — see the dedicated C++ STL: Heaps & Priority Queues post. Here we focus on the correspondence with the data structure.

The Default Is a MAX-Heap

This is the single most common surprise. std::priority_queue defaults to std::less, and that yields a max-heap — top() is the largest element.

#include <queue>

std::priority_queue<int> pq;      // MAX-heap by default
pq.push(3); pq.push(9); pq.push(5);
pq.top();                          // 9, not 3

Meanwhile std::map, std::set and std::sort also default to std::less and give you ascending order. So the same comparator produces smallest-first everywhere else and largest-first here. That inconsistency is the source of the confusion, and it is worth understanding rather than memorising.

Getting a Min-Heap

Flip the comparator to std::greater. The template signature requires you to name the container explicitly, because Compare is the third parameter:

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

std::priority_queue<int, std::vector<int>, std::greater<int>> minpq;
minpq.push(3); minpq.push(9); minpq.push(5);
minpq.top();                       // 3

Since C++14 you can write std::greater<> and let it deduce. A common shorthand worth keeping in a header:

template <class T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

MinHeap<int> pq;                   // reads much better at the call site

The negation trick — pushing -x into a max-heap to simulate a min-heap — works for signed integers and is popular in contests for its brevity. Be aware of its failure modes: it breaks on unsigned types, on floating point with signed zero, and on INT_MIN (whose negation is UB). It also makes the code lie about its intent. Prefer std::greater in anything you will read again.

Mapping to What We Built

Note pop() returns void. To consume the top you must read it first — a deliberate design choice, because returning by value while popping cannot be made exception-safe:

int best = pq.top();      // read
pq.pop();                 // then remove

The std::*_heap Algorithms

std::priority_queue is an adaptor: it wraps a container and hides it, so you cannot iterate the elements. When you need the underlying array — to inspect it, to sort it in place, or to implement something the adaptor does not expose — use the algorithm family directly on any random-access range:

#include <algorithm>
#include <vector>

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

std::make_heap(v.begin(), v.end());        // O(n)   -> max-heap
std::is_heap  (v.begin(), v.end());        // O(n)   -> validity check

v.push_back(11);
std::push_heap(v.begin(), v.end());        // O(log n) sift-up the LAST element

std::pop_heap (v.begin(), v.end());        // O(log n) move max to the BACK
int biggest = v.back();
v.pop_back();

std::sort_heap(v.begin(), v.end());        // O(n log n) -> fully sorted ascending

The contract to remember: push_heap assumes the new element is already at the back and everything before it is a valid heap. pop_heap does not remove anything — it swaps the root to the back and re-heapifies the prefix, leaving the erase to you. Both are exactly the sift_up / sift_down from Part 3 with the boundary handling exposed.

Custom Comparators

For your own types, a stateless functor is the clearest option:

struct Task {
    int  priority;
    long deadline;
};

struct ByPriorityThenDeadline {
    bool operator()(const Task& x, const Task& y) const {
        if (x.priority != y.priority) return x.priority < y.priority;  // higher priority first
        return x.deadline > y.deadline;                                 // earlier deadline first
    }
};

std::priority_queue<Task, std::vector<Task>, ByPriorityThenDeadline> queue;

Read it through the “top = sorts last” rule: x.priority < y.priority returns true when x is less important, so the highest priority sorts last and lands on top. The tie-break reverses the comparison because a smaller deadline should win.

A lambda works too, but the type must be threaded through the template, so it is wordier:

auto cmp = [](const Task& x, const Task& y) { return x.priority < y.priority; };
std::priority_queue<Task, std::vector<Task>, decltype(cmp)> pq(cmp);

Since C++20 a captureless lambda is default-constructible, so the (cmp) argument can be dropped. Before C++20 it is mandatory — omitting it fails to compile.

What the Adaptor Cannot Do

Four hard limitations, each of which motivates a later post:

• No iteration. The container is a protected member; there is no begin(). Use std::make_heap on your own vector if you must inspect elements.
• No decrease-key. You cannot reach in and lower an element's priority. This is the operation Dijkstra classically wants — Part 12 covers indexed heaps and the lazy-deletion workaround.
• No erase of an arbitrary element. Same reason; same workaround.
• No merge. Combining two priority queues means draining one into the other, O(m log(n+m)). Structures that merge in O(log n) or O(1) exist — Part 14.

Next

Foundations are complete: you can build a heap by hand or reach for the library one, and you know precisely which operations each supports. Part 6 starts the techniques half of the series with the algorithm that falls straight out of build plus repeated pop.