Heaps & Priority Queues in C++

August 2026 · 16 min read

Two questions come up more than any others, and both are really the same confusion wearing different clothes:

1. “A max-heap contains the largest elements, right? That's why it's called a max-heap?”
2. “I have an array of n integers but I only want a heap of size k. What do I do?”

The answer to the first is no, and understanding why makes the second one fall out immediately. So we start there, before a single line of template syntax.

No, a Max-Heap Does Not “Contain the Largest Elements”

This is the single most common misunderstanding about heaps, and it is worth being blunt about.

std::priority_queue<int> maxHeap;          // the default: a max-heap
maxHeap.push(5);
maxHeap.push(1);
maxHeap.push(9);
maxHeap.push(3);

maxHeap.size();     // 4  — ALL FOUR are in there. Including the 1.
maxHeap.top();      // 9  — this is the only thing "max" refers to

The heap contains 5, 1, 9, 3. It did not keep the big ones and throw away the small ones. A heap never filters anything. Whatever you push is in there until you pop it.

Think of it as a queue where the biggest item always pushes to the front of the line. Everyone is still in the queue. The name only tells you who gets served next.

So the mental model to replace is:

Once that is clear, the second question can actually be answered — because “a heap of size k” is something you have to enforce. The heap will never do it for you.

“I Have n Integers But Only Want a Heap of Size k”

First, disambiguate. This sentence usually means one of two things, and only one of them is interesting:

1. “I want a heap containing only k of the elements — specifically the k largest.” This is what people almost always mean. Read on.
2. “I want a heap over the first k elements.” Then just push k of them and stop. There is no trick: std::priority_queue<int> pq(v.begin(), v.begin() + k);

Assuming you mean the first: you cap the size yourself, by popping whenever the heap grows past k. And here is where the surprise lands.

Why it inverts

You are keeping a set of k winners. Every time a new element arrives you must answer one question: is this better than the worst thing I am currently keeping? And if you admit it, you must throw out that worst thing to stay at size k.

So the element you need instant access to is the weakest of your winners — the eviction candidate. And top() is the only element a heap gives you in $O(1)$.

If you are keeping the k largest, the weakest winner is the smallest of them. You need the smallest at top(). That is a min-heap.

Try it the other way to see the failure. With a max-heap of size k, top() is the largest element you hold — the one you would never want to remove. The element you actually need to evict is buried somewhere in the leaves, and finding it is $O(n)$. The structure would be pointing at exactly the wrong end.

The code

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

// Keep the k LARGEST of n integers, using O(k) memory.
std::vector<int> kLargest(const std::vector<int>& v, int k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> heap;   // MIN-heap

    for (int x : v) {
        heap.push(x);
        if ((int)heap.size() > k) heap.pop();     // over budget: drop the smallest
    }

    std::vector<int> out;
    while (!heap.empty()) { out.push_back(heap.top()); heap.pop(); }
    return out;                                   // ascending order
}

Two lines do the actual work: heap.push(x) then if (size > k) pop(). That pair is the whole “heap of size k” idea. The heap has no size limit of its own — you impose one.

A slightly faster variant skips the push entirely when the element cannot win, which avoids two heap operations for most inputs:

for (int x : v) {
    if ((int)heap.size() < k)      heap.push(x);        // still filling up
    else if (x > heap.top()) {     heap.pop();          // beats the weakest winner
                                   heap.push(x); }
    // else: x cannot make the cut — discard it with one comparison
}

A trace

Keeping the k = 3 largest of [5, 1, 9, 3, 7, 2, 8]. The heap is a min-heap, so top() is always the smallest of what is currently held:

x=5   push          heap {5}           top=5   (filling)
x=1   push          heap {1,5}         top=1   (filling)
x=9   push          heap {1,5,9}       top=1   (full now)
x=3   3 > 1  yes    pop 1, push 3      heap {3,5,9}   top=3
x=7   7 > 3  yes    pop 3, push 7      heap {5,7,9}   top=5
x=2   2 > 5  no     discard            heap {5,7,9}   top=5
x=8   8 > 5  yes    pop 5, push 8      heap {7,8,9}   top=7

result: {7, 8, 9}  — the 3 largest
        top() = 7  — which is also the 3rd largest, for free

Note the bonus in the last line: when the loop ends, heap.top() is the k-th largest element. That is the entire solution to “find the k-th largest” — no extraction loop needed.

Why bother, versus just sorting

The memory column is usually the point. Finding the top 10 of a billion values needs a heap of 10 elements — you never hold the billion. And it is online: the heap holds the correct answer for everything seen so far, at every moment, so the data can arrive from a socket or a log tail with no known end.

If the array is already in memory and you only need the k largest as an unordered set, std::nth_element is $O(n)$ average and will beat this:

std::nth_element(v.begin(), v.begin() + k, v.end(), std::greater<int>());
// v[0..k) are now the k largest, in unspecified order

Knowing that is part of knowing the tool. The heap wins on memory and streaming, not on raw speed for a one-shot in-memory query.

The Three Declarations

Everything else in C++ is one of these three lines.

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

// 1. MAX-HEAP — the default. top() is the LARGEST.
std::priority_queue<int> maxHeap;

// 2. MIN-HEAP — top() is the SMALLEST. All three template arguments are
//    required, because you cannot name the comparator without naming
//    the container that precedes it.
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

// 3. CUSTOM — any strict weak ordering you like.
struct ByAbsValue {
    bool operator()(int a, int b) const { return std::abs(a) < std::abs(b); }
};
std::priority_queue<int, std::vector<int>, ByAbsValue> customHeap;

Because the min-heap spelling is so noisy, put an alias in a header once and never type it again:

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

MinHeap<int> heap;                        // reads like what it is

The One Rule Behind the Comparator

Do not memorise three behaviours. Memorise one sentence:

Run the cases through it. With std::less, comp(a,b) is a < b, so smaller means lower priority; small values sink and the largest surfaces — a max-heap. With std::greater, larger means lower priority; large values sink and the smallest surfaces — a min-heap. Same machinery, opposite verdicts.

Why std::greater seems to do the opposite in std::sort

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

std::sort(v.begin(), v.end(), std::greater<int>());
// {9, 8, 5, 3, 1} — DESCENDING, largest first

std::priority_queue<int, std::vector<int>, std::greater<int>> pq(v.begin(), v.end());
// pq.top() == 1  — MIN-HEAP, smallest first

The two ask the comparator different questions. std::sort reads comp(a,b) == true as “a comes before b in the output”, so with greater the larger goes first. priority_queue reads the same result as “a is worse, so it sinks”. Sort puts “lesser” first; the heap puts “lesser” last.

Custom Comparators

Two forms are worth knowing. A struct with operator() is the default choice — it is stateless, default-constructible, and easy to name:

struct Task { int priority; long deadline; };

struct ByPriority {
    bool operator()(const Task& a, const Task& b) const {
        return a.priority < b.priority;        // highest priority on top
    }
};

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

A lambda works too, but its type must be threaded through the template:

auto cmp = [](const Task& a, const Task& b) { return a.priority < b.priority; };
std::priority_queue<Task, std::vector<Task>, decltype(cmp)> pq(cmp);
//                                                            ^^^^^
// Required before C++20. Since C++20 a captureless lambda is
// default-constructible, so the argument can be dropped.

Multi-key ordering

Getting this wrong is the most common source of subtly broken heaps. Resolve each key completely before falling through to the next:

// BROKEN — the second line is reached even when a.priority > b.priority
bool operator()(const Task& a, const Task& b) const {
    if (a.priority < b.priority) return true;
    if (a.deadline < b.deadline) return true;
    return false;
}

// CORRECT — settle priority first, then break ties on deadline
bool operator()(const Task& a, const Task& b) const {
    if (a.priority != b.priority) return a.priority < b.priority;
    return a.deadline > b.deadline;
}

// SAFEST — let the library build the lexicographic order for you
bool operator()(const Task& a, const Task& b) const {
    return std::tie(a.priority, a.deadline) < std::tie(b.priority, b.deadline);
}

std::tie is the habit worth forming. It is correct by construction and impossible to get the fallthrough wrong.

Pairs and tuples for free

std::pair and std::tuple already compare lexicographically, so a great many problems need no comparator at all — just order the fields by what should dominate:

// order by count, then by value
std::priority_queue<std::pair<int,int>> pq;    // {count, value}

Field order is the ranking. Writing {value, count} by mistake silently sorts by the wrong key — a bug that produces plausible-looking wrong answers rather than a crash.

Strict weak ordering is not optional

Your comparator must be irreflexive (comp(x,x) is false), asymmetric, and transitive. The classic violation is writing <= instead of <:

return a.priority <= b.priority;     // UNDEFINED BEHAVIOUR: comp(x,x) is true

This is not a stylistic point. The library relies on irreflexivity to bound its sift loops, and violating it permits reads past the end of the container. It rarely crashes immediately, which is what makes it nasty. Compile tests with -D_GLIBCXX_DEBUG and libstdc++ will assert on it.

The Member Functions

pq.push(x);        // O(log n)   — also emplace(args...)
pq.top();          // O(1)       — const reference to the extreme element
pq.pop();          // O(log n)   — removes it, returns void
pq.size();         // O(1)
pq.empty();        // O(1)

Two things to internalise. pop() returns void, so you must read before removing — and you must copy, because top() hands back a reference into the underlying vector:

int best = pq.top();     // copy first
pq.pop();                // now safe to use best

const int& bad = pq.top();
pq.pop();
use(bad);                // DANGLING — the element is gone

And there are no iterators. You cannot loop over a priority_queue, inspect it, or erase from the middle. If you need any of that, use std::make_heap on a vector you own, or a std::set.

Build from a range in $O(n)$

std::vector<int> data = load();

std::priority_queue<int> slow;
for (int x : data) slow.push(x);                        // O(n log n)

std::priority_queue<int> fast(data.begin(), data.end()); // O(n) — calls make_heap

If you already have all the elements, the range constructor is both shorter and asymptotically better. Only push in a loop when the elements genuinely arrive one at a time.

The <algorithm> Heap Family

When you need the underlying array — to iterate it, sort it in place, or do something the adaptor hides — use these on any random-access range:

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

v.push_back(x);
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 root to the BACK
int biggest = v.back();
v.pop_back();                                        // you erase it yourself

std::sort_heap(v.begin(), v.end());                  // O(n log n) — ascending

The contract that surprises people: pop_heap removes nothing. It swaps the root to the back and re-heapifies the prefix, leaving the actual erase to you. Hence the pop_heap / back() / pop_back() trio.

Pitfalls

There is no decrease-key

You cannot reach into a priority_queue and lower an element's priority, which is exactly what Dijkstra classically wants. The standard workaround is lazy deletion: push a new entry with the better value and discard stale ones as they surface.

if (nd < dist[v]) { dist[v] = nd; pq.push({nd, v}); }   // push, don't update
...
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;                              // stale entry — skip it

When a heap is the wrong tool

Cheat Sheet

// ---- DECLARE ------------------------------------------------------------
std::priority_queue<int>                                          maxHeap;
std::priority_queue<int, std::vector<int>, std::greater<int>>     minHeap;
std::priority_queue<T,   std::vector<T>,   MyCmp>                 custom;

// ---- THE ONE RULE -------------------------------------------------------
// comp(a,b) == true  =>  a sinks below b.  top() is never judged "lower".
// And: the root should be the element you are most willing to discard.

// ---- SIZE-K -------------------------------------------------------------
// k LARGEST  -> MIN-heap of size k   (evict the smallest kept)
// k SMALLEST -> MAX-heap of size k   (evict the largest kept)
heap.push(x);
if (heap.size() > k) heap.pop();
// afterwards heap.top() is the k-th largest / smallest

// ---- BUILD --------------------------------------------------------------
std::priority_queue<int> pq(v.begin(), v.end());    // O(n), not O(n log n)

// ---- RAW ALGORITHMS (on a vector you own and can iterate) ---------------
std::make_heap(v.begin(), v.end());                  // O(n)
v.push_back(x); std::push_heap(v.begin(), v.end());  // insert
std::pop_heap(v.begin(), v.end()); v.pop_back();     // extract
std::sort_heap(v.begin(), v.end());                  // ascending

Check Yourself

Going Deeper

This post is the C++ surface. For the data structure itself — why the array encoding works, why building is $O(n)$, the sift operations with correctness proofs, and the algorithmic patterns — see the DSA · Heaps series. Particularly relevant here:

• Top-K & the Bounded Heap Pattern part 7 the size-k idea in full, with frequency and distance variants.
• std::priority_queue & the Heap Algorithms part 5 the same API from the data-structures side.
• Pitfalls: Comparators, Overflow & Invalidation part 15 every failure mode above, in depth.
• Indexed Heaps & Lazy Deletion part 12 what to do about the missing decrease-key.

Practice

• LeetCode 703 — Kth Largest in a Stream min-heap the size-k heap, exactly as above.
• LeetCode 215 — Kth Largest in an Array min-heap then redo it with nth_element and compare.
• LeetCode 973 — K Closest Points to Origin max-heap k smallest distances, so the inversion flips the other way.
• LeetCode 347 — Top K Frequent Elements custom a {count, value} pair does the ordering for you.
• LeetCode 23 — Merge k Sorted Lists min-heap one heap entry per list.
• LeetCode 295 — Find Median from Data Stream two heaps a max-heap and a min-heap facing each other.
• LeetCode 743 — Network Delay Time Dijkstra the {dist, node} min-heap with stale-entry skipping.

Quick Reference

• cppreference: std::priority_queue docs the authoritative signature and member list.
• cppreference: heap algorithms docs the whole make_heap family.
• cppreference: the Compare requirement docs the strict-weak-ordering rules.