Chapter 8 · Data Structures on Trees
Binary Heap and priority_queue
The array-shaped tree, why it is fast in practice, and the six uses beyond Dijkstra.
A binary heap is an array holding a complete binary tree with the heap property: a[i] <= a[2i], a[i] <= a[2i+1]. Completeness is what makes it array-indexed (children of i are 2i, 2i+1; parent is i/2), and what makes it cache-friendly — a pointer-based structure with the same guarantees would be 3–5× slower.
The operations, with their real costs
push,pop(extract-min): O(log n) worst case — sift down/up along one root-to-leaf path of length ⌈ log2 n ⌉,- build from an array: O(n), not O(nlog n) — sift every internal node down, bottom-up; the total is ∑h frac{n}{2h+1} h = O(n), which is the standard "count nodes at each height" argument,
top: O(1),- decrease-key: not supported by
std::priority_queue— either erase+reinsert with astd::set(real decrease-key, O(log n)) or push a duplicate and skip stale entries on pop (the lazy version Dijkstra uses), - merge: O(n + m) by concatenating and rebuilding — which is why "small-to-large merging of heaps" (Small-to-Large Merging) is cheap; a leftist/pairing heap gives O(log n) merge if you truly need it.
void sift_down(vector<int>& a, int i) { // 0-indexed array, size n
int n = (int)a.size();
for (;;) {
int l = 2 * i + 1, r = l + 1, m = i;
if (l < n && a[l] < a[m]) m = l;
if (r < n && a[r] < a[m]) m = r;
if (m == i) break;
swap(a[i], a[m]);
i = m;
}
}
void build(vector<int>& a) { // O(n)
for (int i = (int)a.size() / 2 - 1; i >= 0; i--) sift_down(a, i);
}#std::priority_queue, honestly
priority_queue<int, vector<int>, greater<int>> pq; // min-heap
priority_queue<pair<int,int>> pq2; // max by .first then .second
priority_queue<tuple<int,int>, vector<tuple<int,int>>, greater<>> pq3;
struct Cmp { bool operator()(Job&a, Job&b) const { return a.t > b.t; } }; // NOTE: inverted!
priority_queue<Job, vector<Job>, Cmp> pq4;priority_queue is a max-heap under less<>, so a custom comparator must return a > b to get a min-heap — the inversion is the #1 source of "my greedy processed the largest instead of the smallest" bugs. Writing greater<> (transparent comparator, C++14+) removes the doubt.
while (!pq.empty()) {
auto [d, v] = pq.top(); pq.pop();
if (d != dist[v]) continue; // stale: a better key was pushed after this one
...
}It keeps each relaxation in the heap (up to m entries) instead of n, so memory is O(m) and time O(m log m) — and it is the only sane way to do decrease-key with priority_queue.
#Five non-textbook uses
Greedy with a changing key
- K-way merge / "next event": k sorted lists, push each head, pop min, push the successor — O(N log k).
- Median of a stream: two heaps (max-heap lower half, min-heap upper half) balanced to size difference 1 — the standard sliding-window median needs the lazy-deletion variant plus
eraseby value, which is why a multiset/policy-tree is often shorter. - Scheduling: earliest-deadline-first, and Huffman's two-smallest rule (Huffman Coding) — "extract two minima, push their sum" is one loop.
- Dijkstra / A\* — see Dijkstra's Algorithm, where the heap key is the tentative distance.
- Top-k / "keep the k smallest": a max-heap of size k, evict the top when a smaller element arrives — O(n log k) and O(k) memory, which is what "k nearest / k shortest" subroutines do.
std::set supports erase-by-iterator, lower_bound, and iteration in order, at the same O(log n) — so it wins whenever you need removal of an arbitrary element or successor queries. Heaps win on constants (contiguous array) and on push-only workloads. The decision is about which operations you need, not about asymptotics.
Sorting reduces to "insert all, extract all" on a heap, so a comparison-based heap-sort is O(n log n); heapsort's O(n) build is exactly the constant-factor reason it beats "insert one by one" by 2×. This also explains why a heap cannot support decrease-key in o(log n) and extract-min in o(log n) with comparisons only.