Binary heap / priority queue

O(log n) per op

A tree stored in an array where every parent is smaller (or larger) than its children, so the current min or max sits at the root and is always one read away, even as items keep arriving.

Signals

always need the current smallest/largesttop k elementsmerge k sorted listsrunning median while items keep arrivingpriority queue / most urgent next

Template

function kSmallest(nums, k) {
    const heap = []; // max-heap: keeps the k smallest seen so far
    const swap = (i, j) => ([heap[i], heap[j]] = [heap[j], heap[i]]);
    function push(v) {
        heap.push(v);
        let i = heap.length - 1;
        while (i > 0 && heap[(i - 1) >> 1] < heap[i]) { swap((i - 1) >> 1, i); i = (i - 1) >> 1; }
    }
    function pop() {
        const top = heap[0];
        heap[0] = heap.pop();
        let i = 0;
        while (2 * i + 1 < heap.length) {
            let c = 2 * i + 1;
            if (c + 1 < heap.length && heap[c + 1] > heap[c]) c++;
            if (heap[i] >= heap[c]) break;
            swap(i, c); i = c;
        }
        return top;
    }
    for (const x of nums) {
        push(x);
        if (heap.length > k) pop();
    }
    return heap.slice().sort((a, b) => a - b);
}

Looks similar, isn't

Fast sort (merge/quick): A heap keeps the current min/max while data still arrives (top-k, merge-k, running median); sorting needs the whole set up front, so it forces a full re-sort every time a new item shows up.

n up to 1e5..1e6 arrivals, need the current smallest/largest without a full re-sort -> O(log n) per push/pop, O(n log n) total for n operations.

Learn this pattern