Binary heaps and priority queues

A priority queue hands out the most important element first: the next event in a simulation, the closest unvisited node in Dijkstra, the largest of a stream of scores. A binary heap implements one with nothing but a std::vector and some index arithmetic: O(1) to look at the top, O(log n) to insert or remove it, and O(n) to build from a pile of items.

1. A tree that lives in an array

A heap is a complete binary tree — every level full except possibly the last, which fills from the left. That shape needs no pointers: store the nodes level by level and the links become arithmetic.

These are the 0-based formulas. Many textbooks use a 1-based array (children 2i, 2i+1, parent i/2); mixing the two conventions is the classic heap bug.

The heap property: no child is greater than its parent. It says nothing about siblings or cousins — the array above is a valid heap even though 7 < 8 — but it guarantees the maximum is at index 0.

2. Sift up and sift down

Every heap operation is "make a local change, then repair the property along one root-to-leaf path". Paths are ⌊log₂ n⌋ long, hence O(log n).

push: append at the end (the tree stays complete), then sift up — while the new element is greater than its parent, swap them.

pop: the maximum is at the root. Move the last element into the root, shrink by one, then sift down — while some child is greater, swap with the greater child. Swapping with the smaller child would put it above its larger sibling and break the property.

#include <cstddef>
#include <print>
#include <utility>
#include <vector>

// A max-heap of ints, written out in full.
struct IntHeap {
    std::vector<int> a;

    void push(int x) {
        a.push_back(x);
        std::size_t i = a.size() - 1;
        while (i > 0) {
            std::size_t parent = (i - 1) / 2;
            if (a[parent] >= a[i]) break;      // property holds: done
            std::swap(a[parent], a[i]);
            i = parent;
        }
    }

    int pop() {                                // precondition: !a.empty()
        int top = a.front();
        a.front() = a.back();
        a.pop_back();
        std::size_t i = 0, n = a.size();
        for (;;) {
            std::size_t l = 2 * i + 1;
            if (l >= n) break;                 // no children
            std::size_t c = l;
            if (l + 1 < n && a[l + 1] > a[l]) c = l + 1;   // the greater child
            if (a[i] >= a[c]) break;
            std::swap(a[i], a[c]);
            i = c;
        }
        return top;
    }
};

int main() {
    IntHeap h;
    for (int x : {3, 9, 1, 7, 5, 8}) h.push(x);
    std::print("array: ");
    for (int x : h.a) std::print("{} ", x);
    std::print("\npops:  ");
    while (!h.a.empty()) std::print("{} ", h.pop());
    std::println();
}

Notice the comparisons: sift up asks "is my parent smaller?", sift down asks "which child is larger, and is it larger than me?" — one or two comparisons per level.

3. Building a heap in O(n)

Given n items up front, you could push them one by one: O(n log n), and on ascending input every item climbs all the way to the root. Floyd's build-heap does better. Leaves (the last ⌈n/2⌉ nodes) are already one-element heaps; sift down every internal node, from the last one (n/2 - 1) back to the root:

for (std::size_t i = n / 2; i-- > 0;)   // n/2 - 1, …, 1, 0 — and never wraps
    sift_down(a, i, n);

Why O(n)? A node at height h can move at most h levels. About n/2 nodes have height 0, n/4 height 1, n/8 height 2, …, so the total work is n · Σ h/2^(h+1) ≤ n. The many nodes near the bottom are cheap; the few expensive ones near the top don't add up to much. With two comparisons per level that's at most 2n comparisons.

Watch the loop: for (std::size_t i = n / 2 - 1; i >= 0; --i) looks natural and never terminates — an unsigned i is always >= 0, so it wraps to SIZE_MAX (and n / 2 - 1 already wraps for n < 2). i-- > 0 tests first, then decrements.

4. Heapsort

Build a max-heap over the array, then repeatedly swap the root (the maximum) with the last element of the heap part and sift the new root down in the shrunken heap. The sorted suffix grows from the right:

#include <cstddef>
#include <print>
#include <span>
#include <utility>
#include <vector>

void sift_down(std::span<int> a, std::size_t i, std::size_t n) {
    for (;;) {
        std::size_t l = 2 * i + 1;
        if (l >= n) return;
        std::size_t c = (l + 1 < n && a[l + 1] > a[l]) ? l + 1 : l;
        if (a[i] >= a[c]) return;
        std::swap(a[i], a[c]);
        i = c;
    }
}

void heap_sort(std::span<int> a) {
    for (std::size_t i = a.size() / 2; i-- > 0;) sift_down(a, i, a.size());
    for (std::size_t end = a.size(); end > 1; --end) {
        std::swap(a[0], a[end - 1]);   // max to its final place
        sift_down(a, 0, end - 1);
    }
}

int main() {
    std::vector<int> v{5, 2, 9, 1, 5, 6, 0};
    heap_sort(v);
    for (int x : v) std::print("{} ", x);
    std::println();
}

Heapsort is O(n log n) in the worst case with O(1) extra space — but it isn't stable, and its scattered memory accesses make it slower than introsort in practice. (std::sort in libstdc++ falls back to heapsort when quicksort's recursion gets too deep, precisely for that worst-case guarantee.)

5. The standard library

std::priority_queue<T, Container = std::vector<T>, Compare = std::less<T>> is a heap adaptor:

#include <functional>
#include <print>
#include <queue>
#include <string>
#include <vector>

struct Job {
    int priority;
    std::string name;
};

int main() {
    std::priority_queue<int> maxq;                                      // largest on top
    std::priority_queue<int, std::vector<int>, std::greater<int>> minq; // smallest on top
    for (int x : {4, 1, 7}) {
        maxq.push(x);
        minq.push(x);
    }
    std::println("max {} / min {}", maxq.top(), minq.top());

    auto lower = [](const Job& a, const Job& b) { return a.priority < b.priority; };
    std::priority_queue<Job, std::vector<Job>, decltype(lower)> jobs(lower);
    jobs.push({2, "compile"});
    jobs.push({5, "deploy"});
    std::println("next job: {}", jobs.top().name);
}

Three traps:

• The comparator is inverted from what you'd guess. Compare(a, b) means "a has lower priority than b". So std::less gives a max-heap and std::greater a min-heap.
• pop() returns void and top() returns a const&. Read, then pop. That also makes move-only elements awkward.
• No decrease-key, no iteration, no search. If priorities change, see §7.

The same operations exist as algorithms on any random-access range — std::ranges::make_heap, push_heap (after you push_back), pop_heap (then you pop_back), sort_heap, is_heap. Use them when you need the underlying vector, e.g. to rebuild after bulk changes.

6. Worked example: the k largest of a stream

To keep the k largest values seen so far, keep a min-heap of size k: its top is the smallest of the current top k, so it's the one to evict when a bigger value arrives. O(n log k) time, O(k) memory — better than sorting everything when k ≪ n.

#include <functional>
#include <print>
#include <queue>
#include <vector>

std::vector<int> k_largest(const std::vector<int>& stream, std::size_t k) {
    std::priority_queue<int, std::vector<int>, std::greater<int>> best;   // min-heap
    for (int x : stream) {
        if (best.size() < k) {
            best.push(x);
        } else if (k > 0 && x > best.top()) {
            best.pop();          // evict the smallest of the current top k
            best.push(x);
        }
    }
    std::vector<int> out;
    while (!best.empty()) {
        out.push_back(best.top());
        best.pop();
    }
    return out;   // ascending
}

int main() {
    for (int x : k_largest({5, 12, 3, 8, 20, 1, 9}, 3)) std::print("{} ", x);
    std::println();
}

Faded example — your turn

Write k_smallest(stream, k) the same way. Which kind of heap do you need now, what does its top represent, and when do you evict?

std::priority_queue<int /* , ??? */> best;
for (int x : stream) {
    if (best.size() < k) best.push(x);
    else if (k > 0 && /* ??? */) { best.pop(); best.push(x); }
}

7. When priorities change: lazy deletion

Dijkstra's algorithm wants to lower a node's priority after it's queued. A binary heap can't find an element to update without an index, so the usual trick is lazy deletion: push a new entry with the better priority and, when popping, skip entries that are stale.

#include <functional>
#include <print>
#include <queue>
#include <utility>
#include <vector>

int main() {
    std::vector<int> best{7, 4, 9};   // current priority of nodes 0, 1, 2
    using Entry = std::pair<int, int>;   // (priority, node), smallest first
    std::priority_queue<Entry, std::vector<Entry>, std::greater<Entry>> q;
    for (int v = 0; v < 3; ++v) q.push({best[v], v});

    best[2] = 1;          // node 2 improved: push a fresh entry…
    q.push({1, 2});       // …and leave the old (9, 2) behind

    while (!q.empty()) {
        auto [p, v] = q.top();
        q.pop();
        if (p != best[v]) continue;   // stale entry: skip it
        std::println("node {} at priority {}", v, p);
        best[v] = -1;                 // mark done so later duplicates are stale too
    }
}

The heap may hold several entries per node, so it grows to O(edges) rather than O(nodes), but each push and pop is still O(log n). The alternative is an indexed heap that tracks every element's position (updated on each swap) so decrease-key can sift that element up directly — more code, less memory.

Summary

• Store a complete binary tree in an array: children 2i+1, 2i+2, parent (i-1)/2 (0-based).
• Heap property: no child is greater than its parent, so the maximum is at index 0.
• push = append + sift up; pop = move last to root + sift down (towards the greater child). Both O(log n).
• Build with Floyd's bottom-up sift-downs: O(n), at most 2n comparisons. Count down with i-- > 0.
• Heapsort: O(n log n) worst case, O(1) space, not stable.
• std::priority_queue: std::less = max-heap, std::greater = min-heap; pop() returns nothing; no decrease-key — use lazy deletion.