Sift up, sift down & the priority queue

Insert, extract-min, heapsort, and where priority queues show up in graph algorithms. · 11 min read

Insert — sift up

To insert, append the value at the end of the array (keeping completeness), then sift up: while it is smaller than its parent, swap them. It rises until its parent is ≤ it or it becomes the root.

void push(vector<int>& h, int x) {
    h.push_back(x);
    int i = h.size() - 1;
    while (i > 0 && h[(i - 1) / 2] > h[i]) {
        swap(h[i], h[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

Extract-min — sift down

To remove the minimum, take the root, move the last element to the root (keeping completeness), then sift down: repeatedly swap it with its smaller child until both children are ≥ it.

int pop_min(vector<int>& h) {
    int top = h[0];
    h[0] = h.back(); h.pop_back();
    int i = 0, n = h.size();
    while (true) {
        int c = i, l = 2*i+1, r = 2*i+2;
        if (l < n && h[l] < h[c]) c = l;
        if (r < n && h[r] < h[c]) c = r;
        if (c == i) break;
        swap(h[i], h[c]); i = c;
    }
    return top;
}

Interactive visualization: Watch sift-up on insert and sift-down on extract — step through it frame by frame on this page.

Heapsort

Sorting by repeated extraction

build a heap from n items — O(n) with the bottom-up sift-down.
extract-min n times — Each extract is O(log n).
n × O(log n) — Dominates the build.

Result: O(n log n)

Priority queues in the wild

A heap is a priority queue — push and pop-min in O(log n). This is the engine behind Dijkstra and Prim (always expand the cheapest frontier item), Huffman coding, k-way merge, scheduling, and "top-k" problems. In C++ it's std::priority_queue; in Python, heapq (a min-heap of the underlying list).

Practice: Last Stone Weight (Easy) — Repeatedly smash the two heaviest stones — a max-heap.

Practice: K Smallest Elements (Medium) — Return the k smallest values, sorted ascending.

Practice: Merge K Sorted Lists (Hard) — Merge many sorted lists with a min-heap of their heads.