---
title: "Binary Heap and priority_queue"
summary: The array-shaped tree, why it is fast in practice, and the six uses beyond Dijkstra.
difficulty: core
tags: [heap, greedy, priority]
time: log n
space: n
see: [structures/dsu, shortest/dijkstra, advanced-tree/huffman]
---

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.

:::props title="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 $\lceil \log_2 n \rceil$,
- **build from an array**: $O(n)$, not $O(n\log n)$ — sift every internal node down, bottom-up; the total is $\sum_h \frac{n}{2^{h+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 a `std::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" (@advanced-tree/small-to-large) is cheap; a leftist/pairing heap gives $O(\log n)$ merge if you truly need it.
:::

```cpp heap-core.cpp
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
```cpp pq.cpp
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.

:::example title="Lazy deletion, the pattern you want in Dijkstra"
```cpp
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
:::props title="Greedy with a changing key"
1. **K-way merge / "next event"**: $k$ sorted lists, push each head, pop min, push the successor — $O(N \log k)$.
2. **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 `erase` by value, which is why a multiset/policy-tree is often shorter.
3. **Scheduling**: earliest-deadline-first, and Huffman's two-smallest rule (@advanced-tree/huffman) — "extract two minima, push their sum" is one loop.
4. **Dijkstra / A\*** — see @shortest/dijkstra, where the heap key is the tentative distance.
5. **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.
:::

:::note title="Why not a balanced BST?"
`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.
:::

:::example title="n-log-n lower bound, one paragraph"
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.
:::

:::problems
- [[CSES 1073]] Towers | https://cses.fi/problemset/task/1073 | easy | greedy with an ordered container
- [[CSES 1631]] Reading Books | https://cses.fi/problemset/task/1631 | easy | prefix sums + max
:::