Pitfalls: Comparators, Overflow & Invalidation

August 2026 · 21 min read

Heaps fail quietly. A broken comparator does not throw; it returns plausible values for a while and then produces one that is wrong. A dangling reference into a heap does not crash; it reads a value that used to be there. This post collects the failure modes that actually bite, roughly in order of how often they do.

1. Comparators That Are Not Strict Weak Orderings

The most common serious bug, and formally undefined behaviour.

Your comparator must satisfy three properties: irreflexivity (cmp(x,x) is false), asymmetry (if cmp(x,y) then not cmp(y,x)), and transitivity. The standard library assumes all three and may index past the end of the container when they fail.

// BROKEN: cmp(x, x) is true, violating irreflexivity
auto bad = [](const Task& a, const Task& b) { return a.priority <= b.priority; };

// CORRECT
auto good = [](const Task& a, const Task& b) { return a.priority < b.priority; };

Multi-key comparators are where this most often goes wrong. The naive version silently breaks transitivity:

// BROKEN: when priorities are equal this returns false both ways round,
// but it also reports a < b and b < a as false for genuinely different tasks
bool operator()(const Task& a, const Task& b) const {
    if (a.priority < b.priority) return true;
    if (a.deadline < b.deadline) return true;      // reached even when a.priority > b.priority
    return false;
}

// CORRECT: settle each key completely before moving to the next
bool operator()(const Task& a, const Task& b) const {
    if (a.priority != b.priority) return a.priority < b.priority;
    return a.deadline < b.deadline;
}

// Or let the library do it
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 safest habit — it produces a correct lexicographic ordering by construction, and it is impossible to get the fallthrough wrong.

2. Getting the Heap Direction Backwards

Covered in Part 5 and Part 7, but it deserves restating because it is so frequent:

• std::priority_queue with the default std::less is a max-heap.
• To find the k largest, you keep a min-heap of size k.
• To sort ascending with heapsort, you build a max-heap.

All three feel inverted the first several times. The unifying rule: the root must always be the element you are most willing to give up.

3. Overflow Inside the Comparator

Especially insidious, because overflow does not merely give a wrong number — it breaks the ordering axioms and reintroduces bug #1.

// BROKEN: a.x - b.x overflows for large opposite-signed values
bool operator()(const P& a, const P& b) const { return a.x - b.x < 0; }

// CORRECT
bool operator()(const P& a, const P& b) const { return a.x < b.x; }

The subtract-and-compare idiom is common in code ported from C or Java and is wrong in all of them. Compare directly.

Watch accumulations too. In Part 7's k-closest-points, x*x + y*y needs long long the moment coordinates exceed ~46,000. And in Part 10's CPU scheduler, summing n durations of 10⁹ each overflows int almost immediately.

4. References Invalidated by Mutation

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

top() returns a reference into the underlying container. pop destroys that element, and push may reallocate the vector, invalidating every outstanding reference. Copy before mutating:

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

5. Mutating an Element Already in the Heap

std::priority_queue<Task*> pq;
// ...
someTask->priority = 99;   // the heap has no idea; nothing re-sifts

The heap invariant is established at insertion time. Changing the key of a resident element corrupts the structure silently, and the corruption surfaces later as an out-of-order pop. If you need this, use lazy deletion or an indexed heap from Part 12.

The same applies to heaps of pointers where the pointed-to object is mutated elsewhere — a very easy mistake in a codebase where the objects have other owners.

6. Reading top() on an Empty Heap

std::priority_queue::top() on an empty queue is undefined behaviour, not an exception. It typically returns garbage rather than crashing.

while (!pq.empty()) { auto x = pq.top(); pq.pop(); ... }   // correct

for (int i = 0; i < k; ++i) { auto x = pq.top(); pq.pop(); }  // UB if size < k

The second form appears constantly in top-k code where fewer than k elements were actually inserted.

7. Expecting Stability

Heaps are not stable: equal elements emerge in unspecified relative order, and it can differ between runs or implementations. If insertion order must break ties, put a sequence number in the key:

struct Item {
    int priority;
    long seq;                       // monotonically increasing at insertion
};

struct Cmp {
    bool operator()(const Item& a, const Item& b) const {
        if (a.priority != b.priority) return a.priority < b.priority;
        return a.seq > b.seq;       // earlier insertion wins
    }
};

This also removes any dependence on unspecified behaviour, which makes tests deterministic.

8. Using a Heap When Something Else Is Better

The sliding-window-maximum row is worth dwelling on: it is a common interview question where the heap answer is accepted but the monotonic deque is asymptotically better. Knowing when your tool is second-best is part of knowing the tool.

Review Checklist

1. Is the comparator a strict weak ordering? Does it use < and never <=?
2. Multi-key comparison written with std::tie or with complete per-key resolution?
3. Min-heap or max-heap — and does it match what the algorithm actually needs?
4. Any arithmetic inside the comparator that could overflow?
5. Is top() copied before any mutation?
6. Are elements immutable while resident in the heap?
7. Is empty() checked before every top()?
8. Are ties broken deterministically if that matters?
9. Under lazy deletion, is a live count tracked separately from heap.size()?
10. Is a heap even the right structure here?