Priority queues and heaps

Max/min heaps, custom comparators, multisource tricks, and pairing with lazy updates.

std::priority_queue defaults

priority_queue<T> is a max-heap by default: largest top(), push, pop in O(log n).

Min-heap tricks:

Store negated values for integers.
Or use priority_queue<T, vector<T>, greater<T>> for a min-heap when T has operator> (works for int, long long, pair with default greater lexicographic on min-heap — verify behavior for pairs!).

Custom comparator: third template parameter is Compare such that Compare(a,b) returns true if a is ordered after b (i.e. worse priority) — the naming confuses everyone; copy a known snippet and test on samples.

Example — max-heap (largest on top):

priority_queue<int> pq;
pq.push(3); pq.push(10); pq.push(4);
while (!pq.empty()) {
    int x = pq.top();
    pq.pop();
}

Example — min-heap with greater:

priority_queue<int, vector<int>, greater<int>> mn;
mn.push(3); mn.push(1);
int smallest = mn.top();  // 1

Example — min-heap via negation:

priority_queue<int> mx;
mx.push(-5); mx.push(-2);
int realMin = -mx.top();  // 2

Dijkstra pattern

Store (dist, vertex) in a min-heap; pop smallest dist. If stale (dist > best known), skip (lazy deletion).

Why lazy: decreasing a key in priority_queue is not supported; pushing an improved distance is simpler.

Complexity: O((V+E) log V) with binary heap; STL priority_queue is enough for most contest limits.

Example — Dijkstra (non-negative weights):

const long long INF = (1LL << 62);
int n = ...;
vector<vector<pair<int,int>>> g(n);  // to, w
vector<long long> d(n, INF);
d[s] = 0;
using P = pair<long long,int>;
priority_queue<P, vector<P>, greater<P>> pq;
pq.push({0, s});
while (!pq.empty()) {
    auto [du, u] = pq.top();
    pq.pop();
    if (du != d[u]) continue;  // stale
    for (auto [v, w] : g[u]) {
        if (d[v] > du + w) {
            d[v] = du + w;
            pq.push({d[v], v});
        }
    }
}

Multi-source BFS / 0-1 BFS vs heap

Unweighted multi-source → BFS with all sources in queue initially.

Weighted non-negative multi-source → push all sources with distance 0 (or given costs) into priority_queue and run Dijkstra.

Negative edges → priority_queue Dijkstra fails; you need Bellman-Ford / SPFA (not STL heap) or Johnson with reweighting.

Example — multi-source Dijkstra:

priority_queue<P, vector<P>, greater<P>> pq;
for (int s : sources) {
    d[s] = 0;
    pq.push({0, s});
}
// same pop/relax loop as single-source; duplicate sources just add redundant pushes

Example — merge K sorted lists with heap (smallest head each step):

using T = tuple<int,int,int>;  // value, listId, index
priority_queue<T, vector<T>, greater<T>> pq;
// push (a[i][0], i, 0) for each list i, then repeatedly pop and push next

Storing pairs in the heap

Common: priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> for min by (first, then second). First component is often distance; second breaks ties or carries vertex id.

Always run a tiny custom case on paper — comparator mistakes are instant WA.

Example — pair min-heap (compare first, then second):

using P = pair<int,int>;
priority_queue<P, vector<P>, greater<P>> pq;
pq.push({5, 1});
pq.push({5, 0});  // smaller second wins when first ties
auto [d, id] = pq.top();

Example — custom struct with explicit comparator (max-heap by t, min id tie-break):

struct Job { int t, id; };
struct Cmp {
    bool operator()(const Job& a, const Job& b) const {
        if (a.t != b.t) return a.t < b.t;   // larger t has higher priority
        return a.id > b.id;
    }
};
priority_queue<Job, vector<Job>, Cmp> pq;

Complexity

push / pop: O(log n). top: O(1). Memory O(n) for n stored items (including lazy duplicates in graph algorithms).

Complexity Analysis

Time Complexity

O(log n) push and pop; O(1) top

Space Complexity

O(n) elements in the heap

Dijkstra may hold multiple entries per vertex; lazily ignore outdated pairs

Growth Rate Comparison