Binary Heap / Priority Queue

A complete binary tree stored in an array, satisfying the heap property: every node is $\le$ (min-heap) or $\ge$ (max-heap) its children.

Array layout

For a 0-indexed array: node $i$ has children $2i+1$ and $2i+2$, and parent $\lfloor (i-1)/2\rfloor$. No pointers, perfect cache locality.

Operation	Cost
top	$O(1)$
push	$O(\log n)$ — append, then sift up
pop	$O(\log n)$ — move the last element to the root, sift down
build from an array	$O(n)$ — sift down from the last internal node backwards
decrease-key	$O(\log n)$, but needs an index map
merge two heaps	$O(n)$ — binary heaps do not merge cheaply

Build is $O(n)$, not $O(n\log n)$: most nodes are near the leaves and sift down only a little. The sum ${\sum }_h\frac{n}{2^{h+1}}\cdot h$ converges to $O(n)$.

In C++

priority_queue<int> maxHeap;                                        // max by default
priority_queue<int, vector<int>, greater<int>> minHeap;             // min
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;  // Dijkstra
 
// custom comparator
auto cmp = [](const Item& a, const Item& b) { return a.cost > b.cost; };  // min-heap
priority_queue<Item, vector<Item>, decltype(cmp)> q(cmp);
 
// build in O(n)
priority_queue<int> h(a.begin(), a.end());

The comparator is inverted

priority_queue puts the element the comparator considers largest on top. So greater<> yields a min-heap, and a custom cmp returning a > b also yields a min-heap. This trips up nearly everyone at least once.

No decrease-key — use lazy deletion instead

std::priority_queue cannot update an element. The standard workaround, and the one used in every Dijkstra implementation:

pq.push({newDist, v});                      // push a new entry, leave the stale one
...
auto [d, u] = pq.top(); pq.pop();
if (d > dist[u]) continue;                  // skip stale entries

The queue grows to $O(E)$ instead of $O(V)$, but the complexity is unchanged and the code is much simpler than an indexed heap.

When you genuinely need decrease-key (or erase), use std::set as a heap — $O(\log n)$ for everything including deletion, at the cost of a worse constant.

The heap family

Heap	push	pop	decrease-key	merge
Binary	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(n)$
Binomial	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$
Fibonacci	$O(1)$ am.	$O(\log n)$ am.	$O(1)$ am.	$O(1)$
Pairing	$O(1)$	$O(\log n)$ am.	$O(\log n)$ am.	$O(1)$
Leftist / skew	$O(\log n)$	$O(\log n)$	—	$O(\log n)$

Binary heaps win in practice on constant factor; the others exist for their merge or decrease-key. See Advanced Heaps.

Uses

• Dijkstra, Prim, A*
• Huffman coding — repeatedly merge the two smallest
• Heap sort — $O(n\log n)$, in place, not stable
• $k$-th largest, top $k$ — keep a size-$k$ min-heap
• Merging $k$ sorted lists — heap of list heads, $O(N\log k)$
• Median of a stream — two heaps, a max-heap for the lower half and a min-heap for the upper
• Event simulation / sweep lines — process events in time order
• Slope trick — the entire technique is two heaps

The two-heap median trick

Maintain lo (max-heap, smaller half) and hi (min-heap, larger half), rebalancing so their sizes differ by at most 1. The median is lo.top() (odd count) or the average of both tops (even). $O(\log n)$ per insertion — a fifteen-line answer to “running median”, which is otherwise awkward.

See also: Advanced Heaps · Sorting · Dijkstra