Heaps and Priority Queues
The binary heap invariant and array layout, sift-up and sift-down, O(n) heap construction, std::priority_queue, and heap-based solutions to top-k, k-way merge and running median.
What you will learn
The binary heap invariant and array layout, sift-up and sift-down, O(n) heap construction, std::priority_queue, and heap-based solutions to top-k, k-way merge and running median.
Prerequisites: Module 11 (array representation of complete trees).
Concepts
Min-heap, max-heap, heap property, complete binary tree, array indexing, sift-up, sift-down, heapify, insertion, extract-min/max, and build-heap.
In a max-heap every parent is at least as large as its children, so the maximum is at the root (index 0). The tree is complete, so it lives in an array with no gaps.
Syntax
priority_queue<int> maxHeap;
maxHeap.push(4);
maxHeap.push(10);
int largest = maxHeap.top();
maxHeap.pop();
priority_queue<int, vector<int>, greater<int>> minHeap;Complexity
Peek O(1), insert/extract O(log n), build heap O(n).
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Inserting n descending keys one at a time sifts each new key all the way up — about n log₂ n swaps. Bottom-up heapify sifts down from the last parent; most nodes are near the bottom and move only a little, and the total is bounded by Σ (n / 2^(h+1)) · h = O(n). The run shows the difference growing with n.
#include <bits/stdc++.h>
using namespace std;
struct MinHeap {
vector<int> a;
long long swaps = 0;
void siftUp(size_t i) {
while (i > 0 && a[(i - 1) / 2] > a[i]) { swap(a[(i - 1) / 2], a[i]); ++swaps; i = (i - 1) / 2; }
}
void siftDown(size_t i) {
while (true) {
size_t l = 2 * i + 1, r = l + 1, m = i;
if (l < a.size() && a[l] < a[m]) m = l;
if (r < a.size() && a[r] < a[m]) m = r;
if (m == i) return;
swap(a[i], a[m]); ++swaps; i = m;
}
}
void push(int x) { a.push_back(x); siftUp(a.size() - 1); }
int pop() { int top = a[0]; a[0] = a.back(); a.pop_back(); if (!a.empty()) siftDown(0); return top; }
void build(vector<int> v) { a = move(v); for (size_t i = a.size() / 2; i-- > 0;) siftDown(i); } // bottom-up heapify
};
int main() {
MinHeap h;
for (int x : {5, 3, 8, 1, 9, 2}) {
h.push(x);
cout << "push " << x << " -> array:";
for (int v : h.a) cout << ' ' << v;
cout << '\n';
}
cout << "pop order:";
while (!h.a.empty()) cout << ' ' << h.pop();
cout << '\n';
for (int n : {1000, 100000, 1000000}) {
vect
…push 5 -> array: 5
push 3 -> array: 3 5
push 8 -> array: 3 5 8
push 1 -> array: 1 3 8 5
push 9 -> array: 1 3 8 5 9
push 2 -> array: 1 3 2 5 9 8
pop order: 1 2 3 5 8 9
n=1000: 7987 swaps inserting one by one, 992 swaps with bottom-up build
n=100000: 1468946 swaps inserting one by one, 99990 swaps with bottom-up build
n=1000000: 17951445 swaps inserting one by one, 999988 swaps with bottom-up buildApplications
Heap sort, top-k elements, kth largest/smallest, merge k sorted lists, running median, scheduling, Dijkstra, Prim, and event simulation.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
#include <bits/stdc++.h>
using namespace std;
int main() {
// top-k largest with a min-heap of size k: O(n log k)
vector<int> a = {7, 2, 19, 4, 11, 15, 3, 8, 23, 6};
int k = 3;
priority_queue<int, vector<int>, greater<int>> top;
for (int x : a) { top.push(x); if ((int)top.size() > k) top.pop(); }
cout << "kth (3rd) largest = " << top.top() << '\n';
// merge k sorted lists
vector<vector<int>> lists = {{1, 4, 9}, {2, 3, 10, 12}, {5, 6}};
using T = tuple<int, int, int>; // value, list, index
priority_queue<T, vector<T>, greater<T>> pq;
for (int i = 0; i < (int)lists.size(); ++i) pq.emplace(lists[i][0], i, 0);
cout << "merged:";
while (!pq.empty()) {
auto [v, li, idx] = pq.top(); pq.pop();
cout << ' ' << v;
if (idx + 1 < (int)lists[li].size()) pq.emplace(lists[li][idx + 1], li, idx + 1);
}
cout << '\n';
// running median with two heaps
priority_queue<int> low; // max-heap: smaller half
priority_queue<int, vector<int>, greater<int>> high; // min-heap: larger half
cout << "running medians:";
for (int x : {5,
…kth (3rd) largest = 15
merged: 1 2 3 4 5 6 9 10 12
running medians: 5 10 5 4 5 6Advanced heap families
Binomial heap, Fibonacci heap, pairing heap, d-ary heap, indexed priority queue, decrease-key, lazy deletion, and practical trade-offs versus binary heaps.
Decrease-key: std::priority_queue cannot change a priority in place. The common workaround is lazy deletion — push a new entry and skip outdated ones when popped (Dijkstra in Module 31 does this). An indexed priority queue tracks each item's array position so it can sift in place.
Fibonacci heaps offer amortized O(1) decrease-key, improving Dijkstra's bound to O(E + V log V), but their constant factors make binary or pairing heaps faster in most real programs.
d-ary heaps have shallower trees (cheaper sift-up) and better cache use, at the cost of more comparisons per sift-down.
Practice
Easy: last stone weight — repeatedly smash the two heaviest stones.
Medium: k closest points to the origin.
Hard: sliding-window median.
Quiz
? Why keep a min-heap of size k to find the k largest values?
+ The heap's minimum is the smallest of the current top k, so it is the one to evict — O(n log k) overall. :: A max-heap of all n values costs O(n log n) to build by insertion.
- Min-heaps are faster than max-heaps. :: They are the same.
- To sort the array. :: Not needed.
- It is required by C++. :: No.
? Why is bottom-up heapify O(n) rather than O(n log n)?
+ Most nodes are near the leaves and sift down only a few levels; the sum of heights is O(n). :: The run shows far fewer swaps than one-by-one insertion.
- It skips the leaves entirely. :: True but not sufficient on its own.
- It uses a different comparison. :: No.
- It is O(n log n). :: It is O(n).
? std::priority_queue lacks decrease-key. What do Dijkstra implementations usually do?
+ Push a new entry and skip stale ones when they are popped (lazy deletion) :: Simple and fast in practice.
- Rebuild the heap each time :: O(n) per update.
- Use a stack :: Wrong order.
- Use a Fibonacci heap always :: Possible but rarely faster in practice.