iii. Heaps

The binary heap is the default priority queue. The other heaps exist for meld, global add, monotone keys or decrease-key. Several classic tricks (lazy deletion, two heaps, top- $k$ sums) handle what priority_queue can’t do directly.

Binary heap facts

Array layout: children of $i$ are $2 i + 1$ and $2 i + 2$ (0-indexed).
Push and pop are $O (lo g n)$ . Building from an array is $O (n)$ , because $\sum_{h} \frac{n}{2 ^{h + 1}} h = O (n)$ .

Proof: build-heap (sift-down from the last internal node) is $O (n)$

In a complete binary tree on $n$ nodes, the number of nodes at height $h$ (distance to its deepest descendant leaf, so leaves have $h = 0$ ) is at most $⌈ n / 2^{h + 1} ⌉$ , and sifting a node at height $h$ down costs $O (h)$ in the worst case. Total work is $\sum_{h \geq 0} \frac{n}{2 ^{h + 1}} \cdot h = \frac{n}{2} \sum_{h \geq 0} \frac{h}{2 ^{h}}$ . The series $\sum_{h \geq 0} h / 2^{h}$ converges to a constant ( $= 2$ , by the standard identity $\sum h x^{h} = x / (1 - x)^{2}$ at $x = \frac{1}{2}$ ), so the total is $O (n)$ — in contrast to inserting $n$ elements one at a time top-down, which is $\sum_{h} \frac{n}{2 ^{h + 1}} \cdot (lo g n - h) = O (n lo g n)$ because most nodes are being sifted from the root rather than toward it. $■$

priority_queue puts the element the comparator ranks largest on top, so greater<> gives a min-heap.
No decrease-key: push the new key and skip stale entries when popped (lazy deletion). The heap grows to $O (m)$ but the complexity is unchanged.

Erasable heap (lazy deletion of arbitrary values): keep a second heap of “to delete” values and pop both while their tops match.

struct ErasableHeap {                         // max-heap with erase(x) for values that are present
    priority_queue<ll> a, d;
    void push(ll x) { a.push(x); }
    void erase(ll x) { d.push(x); }
    ll top() { while (!d.empty() && a.top() == d.top()) a.pop(), d.pop(); return a.top(); }
};

The heap family

Heap	push	pop	decrease-key	meld	Use
binary	$lo g n$	$lo g n$	$lo g n$ with index map	$O (n)$	default
leftist	$lo g n$	$lo g n$	—	$lo g n$ worst	meld, persistent heaps (Eppstein)
skew	$lo g n$ am.	$lo g n$ am.	—	$lo g n$ am.	shortest meldable code
randomized meldable	$lo g n$ exp.	$lo g n$ exp.	—	$lo g n$ exp.	10 lines
pairing (PBDS)	$1$	$lo g n$ am.	$lo g n$ am.	$1$	meld + decrease-key ready-made
Fibonacci	$1$ am.	$lo g n$ am.	$1$ am.	$1$	theory only; slower in practice
binomial	$1$ am.	$lo g n$	$lo g n$	$lo g n$	$lo g n$ worst-case meld without randomisation
Brodal queue	$1$	$lo g n$	$1$	$1$	theory only — the provably-optimal bounds, never implemented in practice
hollow heap	$1$	$lo g n$ am.	$1$ am.	$1$	theory only
soft heap	$1$ am.	$1$ am.	—	$1$	corrupts an $ε$ -fraction of keys, see below
radix heap	$O (lo g C)$ am.				monotone integer keys (Dijkstra)

// leftist heap, persistent-friendly (copy on merge for persistence)
struct LNode { ll key; int dist = 1; LNode *l = nullptr, *r = nullptr; };
LNode* meld(LNode* a, LNode* b) {
    if (!a || !b) return a ? a : b;
    if (a->key > b->key) swap(a, b);                 // min-heap
    a->r = meld(a->r, b);
    if (!a->l || a->l->dist < a->r->dist) swap(a->l, a->r);
    a->dist = (a->r ? a->r->dist : 0) + 1;
    return a;
}

Proof: leftist heap merge is $O (lo g n)$ worst case

dist(v) (the null-path length) is the shortest distance from $v$ to a nullptr child, and the leftist invariant keeps dist(\text{left child}) \ge dist(\text{right child}) at every node — so the right spine (follow right children from the root) is the shortest path to a leaf, meaning the right spine of a tree with $k$ nodes on it has length $O (lo g n)$ : each step down the right spine at least halves the number of nodes reachable from there (a node with right-spine-length $d$ has, by induction, at least $2^{d} - 1$ descendants, since both its subtrees have null-path length $\geq d - 1$ ). meld only ever recurses down the right spines of both input heaps (always merging into the right child, with a possible left/right swap after to restore the invariant), so the recursion depth — and hence the total work, each step $O (1)$ — is bounded by the sum of the two right-spine lengths, $O (lo g n)$ . $■$

Making it persistent means allocating a copy of a before modifying it. That’s exactly what Eppstein’s $k$ shortest paths needs (K Shortest Paths).

Skew heap: drop the null-path-length bookkeeping entirely and unconditionally swap children after every merge (still always merging into the right child first). Shorter code than leftist, same asymptotics, but only amortized rather than worst-case.

Proof (cited): skew heap merge is $O (lo g n)$ amortized

Unlike the leftist heap’s worst-case bound above (which relies on the null-path-length invariant skew heaps don’t maintain), the skew heap’s amortized bound needs a potential-function argument (Sleator and Tarjan, 1986): call a node “heavy” if its right subtree has more nodes than its left, “light” otherwise, and show the number of light nodes on the right spine of either input is $O (lo g n)$ , while the unconditional swap at every merge step flips the heavy/light status of nodes it touches, so a potential of (number of heavy right-spine nodes) pays for the “expensive” heavy nodes visited. The full accounting is standard but intricate and not reproduced here.

Meldable heaps (or small-to-large with priority_queue, $O (n lo g^{2} n)$ ) matter for: merging children’s heaps in tree greedy problems, the $O (E lo g V)$ directed MST (Chu-Liu/Edmonds with melded incoming edges), and slope trick on trees.

Why Fibonacci heaps are a trap: the $O (1)$ amortized decrease-key improves Dijkstra from $O (E lo g V)$ to $O (E + V lo g V)$ on paper, but the constant factor and pointer-chasing make it slower than a binary heap for every graph size that fits in memory — nobody uses it in contests, few use it in production. The lesson generalises: an asymptotic win bought with a large constant and poor cache behaviour is usually not a win. Soft heaps (Chazelle) go the other way: allow $O (1)$ amortized everything by deliberately corrupting at most an $ε$ fraction of keys (their stored value may be increased), used to break the $Ω (n lo g n)$ sorting-based barrier for MST and for a clean linear-time selection algorithm — a genuinely surprising idea, giving up exactness for constant-time operations.

Global add (offset trick)

Store values relative to a global offset, so “add $x$ to every element” is $O (1)$ . Combined with small-to-large merging (move the smaller heap’s elements, adjusting for both offsets), you get mergeable heaps with global add in $O (n lo g^{2} n)$ total. That’s the core of slope trick on trees and many tree-greedy problems.

Proof: the global-offset trick preserves heap order and correctness

If every logical value $v_{i}$ is stored as $v_{i} - offset$ , the heap’s internal ordering by stored value is identical to the ordering by logical value (subtracting the same constant from every key preserves all pairwise comparisons), so top/pop on stored keys still returns the logically-smallest element — just reported as stored value plus offset. addAll(x) simply increments offset, an $O (1)$ change to a single shared constant that instantly and correctly shifts every element’s logical value by $x$ , since every future read adds back the (now larger) offset. Merging two heaps with different offsets by re-inserting the smaller one’s elements with top()+o.offset (i.e. converting to the absolute value, then re-subtracting the surviving heap’s own offset on push) is exactly consistent rebasing, so the merged heap’s logical multiset is the union of the two original ones. Small-to-large (always moving the smaller heap’s $k$ elements) gives each element $O (lo g n)$ moves over the structure’s lifetime (same argument as small-to-large on trees), so total work is $O (n lo g n \cdot lo g n) = O (n lo g^{2} n)$ (the extra $lo g n$ factor is the $O (lo g n)$ heap push per moved element). $■$

Radix heap

For Dijkstra with non-negative integer weights: keys are pushed in non-decreasing order relative to the last popped key. Bucket $i$ holds keys whose highest bit differing from last is $i - 1$ . Popping redistributes the first non-empty bucket around its minimum, and each element moves down at most $lo g C$ times.

Proof: radix heap pop is $O (lo g C)$ amortized

bucket(x, last) returns $1 + ⌊ lo g_{2} (x \oplus l a s t)⌋$ (or $0$ if $x = l a s t$ ), i.e. the position of the highest bit where $x$ differs from the last popped key — so bucket $i$ holds exactly the keys in a range of width $2^{i - 1}$ around last. Since Dijkstra only pops keys in non-decreasing order, once last advances past a key it never needs to move to a higher bucket again; redistributing bucket $i$ around its new minimum $l a s t^{'}$ only ever sends an element to a bucket $j < i$ (because every element in bucket $i$ is within $2^{i - 1}$ of the old last, hence within $2^{i - 1}$ of $l a s t^{'} \geq l a s t$ too, and $∣ l a s t^{'} - l a s t ∣ < 2^{i - 1}$ keeps it below bucket $i$ ) — so each element’s bucket index is strictly non-increasing over the heap’s lifetime. An element starts in a bucket $\leq lo g_{2} C$ and can move down at most $lo g_{2} C$ times, each move $O (1)$ (one vector push), so the total work across all pops is $O (n lo g C)$ , giving $O (lo g C)$ amortized per pop. $■$

template<class V> struct RadixHeap {
    array<vector<pair<ull, V>>, 65> b; ull last = 0; size_t cnt = 0;
    static int bucket(ull x, ull l) { return x == l ? 0 : 64 - __builtin_clzll(x ^ l); }
    void push(ull k, V v) { cnt++; b[bucket(k, last)].push_back({k, v}); }
    pair<ull, V> pop() {
        if (b[0].empty()) {
            int i = 1; while (b[i].empty()) i++;
            last = min_element(all(b[i]))->first;
            for (auto& e : b[i]) b[bucket(e.first, last)].push_back(e);
            b[i].clear();
        }
        cnt--; auto e = b[0].back(); b[0].pop_back(); return e;
    }
};

When $max w \cdot n$ is small, Dial’s algorithm (buckets indexed directly by distance) is even simpler (Shortest Paths).

Two-heap patterns

Running median: lo (max-heap, smaller half) and hi (min-heap, larger half), with sizes balanced so that $∣ l o ∣ - ∣ hi ∣ \in {0, 1}$ . The median is lo.top(). With sums of each half, the minimum of $\sum ∣ x_{i} - c ∣$ over $c$ is also $O (1)$ : $c$ = median, cost = sum(hi) - sum(lo) adjusted by sizes.

Proof: the two-heap median and the minimum of $\sum ∣ x_{i} - c ∣$

Maintaining $∣ l o ∣ - ∣ hi ∣ \in {0, 1}$ with every element of lo $\leq$ every element of hi (enforced by rebalancing: whenever a new element would break size balance or the cross-heap order, move the offending top across) means lo holds exactly the $⌈ n /2 ⌉$ smallest elements and hi the rest; the median of a sorted array is its $⌈ n /2 ⌉$ -th smallest element (odd $n$ ) or the average of the two middle elements (even $n$ ), which is exactly lo.top() or the average of both tops. For $\sum_{i} ∣ x_{i} - c ∣$ : this is a convex piecewise-linear function of $c$ with slope $(# {x_{i} < c}) - (# {x_{i} > c})$ , which is zero (minimised) exactly when $c$ splits the multiset into two equal(-ish) halves, i.e. at the median — a standard exchange argument: moving $c$ toward the majority side strictly decreases the sum until the halves balance. At $c = median$ , $\sum ∣ x_{i} - c ∣ = \sum_{x_{i} > c} (x_{i} - c) + \sum_{x_{i} \leq c} (c - x_{i}) = sum (hi) - ∣ hi ∣ \cdot c + ∣ l o ∣ \cdot c - sum (l o)$ , which is the claimed sum(hi) - sum(lo) adjusted by the (known) sizes and median value. $■$

Sliding window median: the same with two multisets (deletion by value), or lazy-deletion heaps with explicit size counters.

Sum of the $k$ largest under insert/erase/change of $k$ : two multisets, top (the $k$ best) and rest, with a running sum of top. After each change, move border elements until top has exactly $min (k, n)$ elements. $O (lo g n)$ per operation. Uses: “sum of the $k$ largest in every sliding window”, “best $k$ items as items arrive and leave”, DP transitions that take the best $k$ options.

struct TopK {                                  // sum of the k largest
    int k; ll s = 0; multiset<ll> top, rest;
    void fix() {
        while (sz(top) > k) { auto it = top.begin(); s -= *it; rest.insert(*it); top.erase(it); }
        while (sz(top) < k && !rest.empty()) { auto it = prev(rest.end()); s += *it; top.insert(*it); rest.erase(it); }
        while (!top.empty() && !rest.empty() && *prev(rest.end()) > *top.begin()) {
            ll a = *top.begin(), b = *prev(rest.end());
            top.erase(top.begin()); rest.erase(prev(rest.end()));
            top.insert(b); rest.insert(a); s += b - a;
        }
    }
    void insert(ll x) { rest.insert(x); fix(); }
    void erase(ll x) { auto it = top.find(x); if (it != top.end()) s -= x, top.erase(it); else rest.erase(rest.find(x)); fix(); }
};

Proof: TopK maintains the sum of the $k$ largest, worst-case $O (lo g n)$ per operation

fix() first restores $∣ t o p ∣ = min (k, n)$ (moving at most one element between the two multisets, since insert/erase change the total size by exactly one), then its final loop restores the cross-set order invariant “every element of top $\geq$ every element of rest” by swapping the smallest of top with the largest of rest whenever that invariant is violated. Once both invariants hold, top holds the $min (k, n)$ largest elements by definition — any set of that size with “all its elements $\geq$ all elements outside it” must be exactly the top elements, since an outside element larger than an inside one would violate the order invariant — so s, updated by exactly the amount each swap/move changes top’s contents, is their sum. Since the invariants held before the call and only one element changed membership in the whole structure, at most one element can now be “out of place” relative to the top/rest boundary: if the size-fixing step already moved an element across, no further swap is needed (the moved element takes exactly the role the boundary required); otherwise at most one swap (the new/removed element against the opposite multiset’s extreme) restores order, because every other pair of elements across the boundary was already correctly ordered before the call. So the final loop runs at most once in substance, and the whole call does $O (1)$ multiset operations, each $O (lo g n)$ — worst-case $O (lo g n)$ per insert/erase, not merely amortized. $■$

Other uses

Merging $k$ sorted lists: heap of list heads, $O (N lo g k)$ .
$k$ -th smallest pair sum $a_{i} + b_{j}$ of two sorted arrays: start from $(0, 0)$ and expand $(i + 1, j)$ and $(i, j + 1)$ with a visited set, or push $(i, 0)$ for all $i$ and advance $j$ only. $O (k lo g k)$ .
$k$ best subsets, or $k$ -th smallest subset sum: a heap of states where each state generates two successors (the “Frederickson-style” or “replace the last element / extend” scheme), so the heap never holds more than $O (k)$ states.
Event simulation and sweep lines, A*, Huffman coding, slope trick (Slope Trick).
Priority-queue undo trick: the heap analogue of the DSU queue-undo trick, for a divide-and-conquer-over-time recursion that needs “push, and later undo the push” on a max/min-heap. A plain heap has no efficient arbitrary-element deletion, so instead of deleting, record every push on a stack and, to undo the last $k$ pushes, pop them off the stack and re-insert everything else still logically present — or, more simply, keep a lazily-deleted heap (push the value with a version tag, and on pop skip anything tagged as undone) so “undo” is $O (1)$ marking and the heap only ever grows, paid for once per real push, same amortized bound as the DSU version.

Binomial heap

A forest of binomial trees $B_{0}, B_{1}, \dots$ ( $B_{k}$ = two $B_{k - 1}$ linked root to root, $2^{k}$ nodes), at most one of each order, like the binary representation of $n$ . Push, pop-min and meld are $O (lo g n)$ (push is $O (1)$ amortized, exactly binary-counter increments). Historically the base of Fibonacci heaps; in contests a pairing heap or __gnu_pbds meldable heap is simpler, but meldability in $O (lo g n)$ worst case is the point.

template <class T> struct BinomialHeap {                  // min-heap with meld
    struct Node { T key; int deg = 0; Node *child = nullptr, *sib = nullptr; };
    vector<Node*> roots;                                  // roots[k]: tree of order k or nullptr
    static Node* link(Node* a, Node* b) { if (b->key < a->key) swap(a, b); b->sib = a->child; a->child = b; a->deg++; return a; }
    void insertTree(Node* t) {                            // binary-counter carry
        for (int k = t->deg;; k++) {
            if (k >= sz(roots)) roots.resize(k + 1, nullptr);
            if (!roots[k]) { roots[k] = t; return; }
            t = link(roots[k], t); roots[k] = nullptr;
        }
    }
    void push(T x) { insertTree(new Node{x}); }
    void meld(BinomialHeap& o) { for (Node* t : o.roots) if (t) insertTree(t); o.roots.clear(); }
    int minIdx() const { int b = -1; for (int i = 0; i < sz(roots); i++) if (roots[i] && (b < 0 || roots[i]->key < roots[b]->key)) b = i; return b; }
    bool empty() const { return minIdx() < 0; }
    T top() const { return roots[minIdx()]->key; }
    void pop() {
        int b = minIdx(); Node* t = roots[b]; roots[b] = nullptr;
        for (Node* c = t->child; c;) { Node* nx = c->sib; c->sib = nullptr; insertTree(c); c = nx; }   // children: orders deg-1..0
        delete t;
    }
};

Proof: binomial trees and the $O (lo g n)$ bounds

By induction $B_{k}$ has $2^{k}$ nodes, height $k$ , and its root has children $B_{k - 1}, \dots, B_{0}$ (linking two $B_{k - 1}$ adds one as the new first child). Heap order is preserved by link (the smaller root stays on top). Since each order appears at most once, a heap of $n$ elements has trees exactly at the set bits of $n$ : at most $⌊ lo g_{2} n ⌋ + 1$ roots, so top scans $O (lo g n)$ roots. insertTree is a binary-counter increment at position $k$ : each carry links two trees in $O (1)$ . pop removes a root of order $d \leq lo g_{2} n$ and re-inserts its $d$ children; meld re-inserts $O (lo g n)$ trees; each insertion’s carries are bounded by the number of orders, so both are $O (lo g^{2} n)$ in this simple form and $O (lo g n)$ with the standard simultaneous merge of the two root lists (a binary addition). Push is $O (1)$ amortized by the binary-counter argument.

Venice Heap

Min-heap that supports “add x to every element” in O(1) and merging heaps by moving the smaller one.

VeniceHeap<i64> h;
h.push(v); h.top(); h.pop(); h.size();
h.addAll(x);                         // every element += x
h.merge(other);                      // other becomes empty

Complexity: O(log n) push/pop, O(1) addAll, merges O(n log^2 n) in total (small to large).
The “Venice technique”: instead of changing every element, store values relative to a global offset, the way water rises around buildings. Common in greedy problems on trees (merge children heaps and shift all keys) and in slope-trick style DP (see dp/slope-trick.cpp).

Implementation

template <class T>
struct VeniceHeap {
    T offset{};
    priority_queue<T, vector<T>, greater<T>> pq;
 
    void push(T v) { pq.push(v - offset); }
    T top() const { return pq.top() + offset; }
    void pop() { pq.pop(); }
    int size() const { return pq.size(); }
    bool empty() const { return pq.empty(); }
    void addAll(T x) { offset += x; }
 
    void merge(VeniceHeap& o) {
        if (size() < o.size()) {
            swap(pq, o.pq);
            swap(offset, o.offset);
        }
        while (!o.pq.empty()) {
            push(o.pq.top() + o.offset);
            o.pq.pop();
        }
        o.offset = T{};
    }
};

whoashish's cp notes

Directory