Advanced Heaps

Heaps beyond the binary heap, and the operations that motivate them: meld (merge two heaps) and decrease-key.

The comparison

Heap	push	pop-min	decrease-key	meld	Practical?
Binary	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(n)$	yes — best constant
Binomial	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	rarely
Leftist	$O(\log n)$	$O(\log n)$	—	$O(\log n)$	yes, when melding
Skew	$O(\log n)$ am.	$O(\log n)$ am.	—	$O(\log n)$ am.	yes — 20 lines
Pairing	$O(1)$	$O(\log n)$ am.	$O(\log n)$ am.	$O(1)$	yes — good constant
Fibonacci	$O(1)$ am.	$O(\log n)$ am.	$O(1)$ am.	$O(1)$	no — huge constant
Randomized meldable	$O(\log n)$ exp.	$O(\log n)$ exp.	—	$O(\log n)$ exp.	yes — 10 lines
Brodal queue	$O(1)$	$O(\log n)$	$O(1)$	$O(1)$	no — theoretical
Hollow heap	$O(1)$	$O(\log n)$ am.	$O(1)$ am.	$O(1)$	no
Soft heap	$O(1)$ am.	$O(1)$ am.	—	$O(1)$	specialised — see Chazelle

Meldable heaps — the ones worth writing

Randomized meldable heap

Ten lines, expected $O(\log n)$ for everything, and it is the easiest meldable heap to get right.

struct Node { int key; Node *l = nullptr, *r = nullptr; };
mt19937 rng(random_device{}());
 
Node* merge(Node* a, Node* b) {
    if (!a || !b) return a ? a : b;
    if (a->key > b->key) swap(a, b);              // min-heap
    if (rng() & 1) swap(a->l, a->r);
    a->l = merge(a->l, b);
    return a;
}
void push(Node*& h, int key) { h = merge(h, new Node{key}); }
void pop(Node*& h)           { h = merge(h->l, h->r); }

The random swap keeps the expected depth $O(\log n)$ without any balancing bookkeeping.

Leftist heap

Deterministic version: store the null-path length at each node and always merge into the shorter side. Guarantees $O(\log n)$ worst case rather than expected.

Skew heap

Leftist without the bookkeeping: always swap children after merging. $O(\log n)$ amortized, and even shorter than the randomized version.

Why melding matters

Melding turns “combine two collections” from $O(n)$ into $O(\log n)$, which matters in:

• Small-to-large on trees — merge children’s heaps in tree DP without the $\log$ from copying
• Chu-Liu/Edmonds — the $O(E\log V)$ implementation melds heaps of incoming edges when contracting cycles
• Eppstein’s $k$ shortest paths — needs persistent meldable heaps
• Offline problems where sets merge irreversibly

Why Fibonacci heaps are a trap

The $O(1)$ amortized decrease-key improves Dijkstra from $O(E\log V)$ to $O(E+V\log V)$ — on paper. In practice the constant factor and the pointer chasing make it slower than a binary heap for every graph size that fits in memory. Nobody uses Fibonacci heaps in contests, and few use them in production.

The lesson generalises: an asymptotic improvement bought with a large constant and poor cache behaviour is usually not an improvement.

Indexed heaps

When you truly need decrease-key without lazy deletion, keep a pos[] array mapping element ids to heap positions and update it during every sift. Adds $O(n)$ memory and some bookkeeping. In practice, lazy deletion (push a duplicate, skip stale entries) is simpler and just as fast.

Soft heaps

Chazelle’s soft heap allows $O(1)$ amortized operations by corrupting at most an $\epsilon$ fraction of keys (their stored values may be increased). Used to break the $\Omega (n\log n)$ barrier in MST and to give a clean linear-time selection algorithm. A genuinely surprising idea: giving up exactness buys constant-time priority queue operations.

See also: Binary Heap · Exotic Structures · Dijkstra