Heaps & Priority Queues Explained: The Binary Heap Behind Always-Next-Urgent

You walk into a hospital emergency room, take a paper token, and sit down. Twenty minutes later a man stumbles in clutching his chest — no token, arrived long after you — and a nurse walks him straight past the whole waiting room and through the doors.

You don’t feel cheated, because you know the rule instinctively: an emergency room isn’t a queue. It’s not first-come-first-served. It’s most-urgent-first, and the whole room quietly re-sorts itself every time someone new walks in. That rule — always hand me the most urgent thing next, no matter when it arrived — is one of the most useful shapes in all of computing. It’s called a priority queue, and the structure that makes it fast is a binary heap. By the end of this article you and I will have built one together, and you’ll know exactly why the most urgent patient surfaces in a single glance.

Let’s start nowhere near a computer

Forget the ER for a second and picture the triage board as a pyramid of people. One person stands at the very top. Below them stand two people; below each of those, two more; and so on, filling in row by row, left to right, with no gaps.

The pyramid obeys exactly one rule: nobody is ever more urgent than the person directly above them. Urgency is a number here, and smaller means more urgent — so a parent’s number is always less than or equal to its two children’s.

Sit with that one rule, because everything falls out of it:

• The most urgent person is always at the very top. Not “usually” — always. If someone more urgent existed anywhere in the pyramid, the rule would have floated them above their manager, and their manager above theirs, all the way to the peak. So “who’s next?” costs you one glance, never a search.
• Notice what the rule does not promise. The person at the top of the left branch and the person at the top of the right branch could be in any order. The pyramid is only sorted up-and-down, never left-to-right. It’s a loose, cheap kind of order — and that looseness is precisely why it’s fast to maintain.

Now, two things happen at a triage board all day: someone new arrives, and the top person gets taken in. Watch how the pyramid heals itself each time, because these two little motions are the entire data structure.

Someone new arrives. They start at the next open spot at the bottom — the only spot that keeps the pyramid gap-free. If they’re more urgent than their manager, the two swap places; the newcomer keeps getting promoted, one level at a time, until they meet a manager more urgent than they are (or they reach the top). A newcomer only ever climbs as many rows as the pyramid is tall.

The top person is taken in. Their spot is now empty, but you can’t leave a hole at the peak. So you grab the last person who joined — the one at the bottom-right — and stand them at the top. They almost certainly don’t belong there, so they demote: they swap down with their more urgent child, and keep sinking until both the people below them out-rank them (or they hit the bottom).

Climb-up on arrival, sink-down on removal, each bounded by the pyramid’s height. Hold onto those two motions — we’re about to give them their real names and, more surprisingly, throw away the pyramid entirely while keeping every bit of its behaviour.

The same shape, all over your day

Once you’ve seen “surface the most urgent, cheaply,” you start noticing priority queues running the machinery around you:

• Your operating system picks which thread runs next off a priority queue — that’s why a keystroke jumps ahead of a background backup.
• Maps and routing. Dijkstra’s algorithm explores the road network by always expanding the nearest-unvisited place next — that “nearest next” is a heap, and it’s the beating heart of the search.
• “Trending now,” “top 10 most expensive,” log analysis — anything that wants the top-k out of a firehose leans on a heap.
• Streaming statistics like a running median lean on two heaps facing each other.

But the most illuminating place to look isn’t a data structure at all — it’s a scheduler with a clock. A game engine, an event simulator, a setTimeout runtime: each holds thousands of pending events, keyed by when they should fire, and forever asks the same question — “what’s the next event due?” That’s a min-heap where the priority is a timestamp, and peek() is the soonest deadline.

Here’s the twist that makes it interesting, the wrinkle a textbook heap doesn’t mention. Timers get cancelled. A user closes the tab; a network reply arrives before its timeout. Now the heap holds an entry for an event that must never fire. You can’t cheaply reach into the middle of a heap and pluck it out, so real schedulers don’t try — they leave the ghost entry in place and simply skip it when it surfaces (“oh, you were cancelled — ignored, O(1)”). That’s lazy deletion, the exact same trick Dijkstra uses for its stale queue entries. Same structure, same escape hatch: a heap is fast at the top and the bottom, and deliberately clumsy in the middle — so good designs arrange to only ever touch the top.

What it actually looks like

Here’s where heaps stop looking like a normal tree and start looking like a magic trick. Let me show you the same heap two ways at once: as the pyramid you already understand, and as a plain flat array.

Look hard at the bottom row of boxes, because that array is the heap. There are no left/right pointers anywhere — no node objects holding references to children. The tree is implied by position. Read the array top-down, left-to-right, and you’ve walked the pyramid level by level.

And the link between the two views is pure arithmetic. For the node sitting at index i:

• its left child is at index 2i + 1
• its right child is at index 2i + 2
• its parent is at index (i - 1) / 2 (integer division)

The blue node in the diagram holds value 2 at index 2; the rule says its children live at 2·2+1 = 5 and 2·2+2 = 6, and sure enough, those are the two teal slots. No pointer chasing — just a multiply and an add.

The one idea that sets heaps apart: a tree with no pointers

This deserves its own section, because it’s the single most beautiful — and most easily missed — thing about heaps. Every other tree you’ve met (a binary search tree, a trie) is a constellation of little node objects, each holding pointers to its children, scattered wherever the allocator happened to put them. A heap throws all of that away and stores the tree in one contiguous block, using position as the only pointer.

Why is that allowed? Because we force the tree to be complete: every level is packed full before the next one starts, and the last level fills strictly left to right. That single constraint is what makes the index math exact — and if you break it, the whole scheme collapses.

On the left, a complete tree drops straight into a gapless array: index is fill-order, and 2i+1 / 2i+2 always land on real children. On the right, punch a hole in the middle. Now you have two bad options, and both lose. Leave a blank slot in the array and you’re wasting space and it’s no longer really a heap. Or pack the survivors tight into [a, c, d] — and now the arithmetic lies to you: it insists a’s children are at indices 1 and 2 (that’s c and d), but d is actually c’s child. The array can only stand in for the tree while the tree has no gaps.

That completeness guarantee isn’t a limitation we tolerate — it’s the whole point, and it buys two things that matter enormously in practice:

Everything else in this article — sift-up, sift-down, heapify — is just careful bookkeeping on top of 2i+1, 2i+2, and (i-1)/2.

Let’s build one, step by step

We’ll build a min-heap (smallest on top) in small pieces, then assemble the whole thing at the end.

Step 1: the array and the three index rules

The state is almost embarrassingly small: a backing array and a count of how many slots are in use. And the three index helpers are the arithmetic we just drew.

private int[] heap = new int[16];
private int size;
 
private static int parent(int i) { return (i - 1) / 2; }
private static int left(int i)   { return 2 * i + 1; }
private static int right(int i)  { return 2 * i + 2; }

That’s the entire skeleton. No Node class, no pointers — a heap really is just an array that agrees to obey one rule.

Step 2: peek — the free lunch

The whole reason we did all this: the smallest element is always at index 0. Not “find the smallest” — it’s already sitting there, put there by the heap property. So peek() is O(1), a single array read.

public int peek() {
    if (size == 0) {
        throw new NoSuchElementException("heap is empty");
    }
    return heap[0];
}

Step 3: insert — park at the end, then climb

To add a value, drop it in the first empty slot — index size, the bottom-right of the tree. That keeps the tree complete, but it probably breaks the heap property, because the newcomer might be smaller than its parent. So we sift it up: while it’s smaller than its parent, swap the two and follow it up.

public void insert(int value) {
    if (size == heap.length) {
        heap = Arrays.copyOf(heap, heap.length * 2);
    }
    heap[size] = value; // park it in the first empty slot
    siftUp(size);       // ...and let it climb
    size++;
}
 
private void siftUp(int i) {
    while (i > 0 && heap[i] < heap[parent(i)]) {
        swap(i, parent(i));
        i = parent(i);
    }
}

Each swap moves the value up exactly one level, and a complete tree of n nodes is only about log₂ n levels tall — so insert is O(log n). The i > 0 guard is what stops the climb at the root, which has no parent to compare against.

Step 4: extract-min — promote the last, then sink

Removing the smallest is the mirror image. The answer is heap[0], but ripping it out would leave a hole at the top. So we take the last element, drop it into the root, shrink the heap, and let that too-big value sift down until it settles.

Sifting down has one rule that trips up half the candidates in interviews, so let’s get it exactly right — and let’s watch it go wrong first.

Here’s the seductive bug. “Sink while a child is smaller than me, swapping with that child” — and, reaching for the first child you wrote, you compare against the left one:

// BUG: only ever looks at the LEFT child.
private void siftDownBuggy(int i) {
    while (left(i) < size && heap[left(i)] < heap[i]) {
        swap(i, left(i));
        i = left(i);
    }
}

Run it on a root of 8 whose children are 3 (left) and 1 (right):

before:  [8, 3, 1]        after siftDownBuggy(0):  [3, 8, 1]
             8                                          3
            / \                                        / \
           3   1                                      8   1   ← 3 sits above 1!

The 8 swapped with the left child 3 and stopped — but now 3 is a parent of 1, and 3 > 1. The heap property is still broken. The fix is one word: always swap with the smaller of the two children, so the value that rises is the smallest of the trio.

public int extractMin() {
    if (size == 0) {
        throw new NoSuchElementException("heap is empty");
    }
    int min = heap[0];
    size--;
    heap[0] = heap[size]; // move the last element into the root
    siftDown(0);          // ...and let it sink
    return min;
}
 
private void siftDown(int i) {
    while (true) {
        int smallest = i;
        int l = left(i);
        int r = right(i);
        if (l < size && heap[l] < heap[smallest]) smallest = l;
        if (r < size && heap[r] < heap[smallest]) smallest = r;
        if (smallest == i) {
            return; // both children out-rank us → done
        }
        swap(i, smallest);
        i = smallest;
    }
}

We look at both children, pick the smaller, and stop the moment neither beats the current node. Same height bound as before, so extract-min is O(log n).

Step 5: heapify — turning a whole array into a heap in O(n)

Say you already have an array of n values and want a heap. The obvious route is n inserts — that’s O(n log n). But there’s a lovely shortcut: treat the array as an already-shaped (but unordered) complete tree, and sift down every non-leaf node, starting from the last one and walking backwards to the root.

public MinHeap(int[] values) {
    heap = Arrays.copyOf(values, Math.max(values.length, 1));
    size = values.length;
    for (int i = size / 2 - 1; i >= 0; i--) { // last non-leaf → root
        siftDown(i);
    }
}

We start at size / 2 - 1 because that’s the last node that has a child — everything after it is a leaf, and a leaf is already a valid one-element heap. Now, the surprise: this loop looks like it runs n/2 sift-downs of O(log n) each, which sounds like O(n log n). It’s actually O(n). Here’s why.

The trick is that a node’s sift-down cost is bounded by its height — how far it can sink — not by the height of the whole tree. And a complete tree is bottom-heavy: half its nodes are leaves (height 0, zero work), a quarter are height 1, an eighth are height 2, and so on. The expensive nodes near the top are vanishingly few. Summed up:

The cheap nodes are many and the dear nodes are few, and the series converges to a small constant. Building a heap costs a single linear pass — cheaper than sorting, which is exactly why heapsort and top-k selection start here.

Step 6: top-k — the counter-intuitive move

Here’s a puzzle that shows off heaps beautifully. A firehose of numbers streams past; you want the k largest, and you can’t hold them all in memory. Sorting the whole stream is O(n log n) and needs all n in hand at once.

The move that surprises everyone: keep a min-heap of size k — a min-heap, to track the largest values. The smallest of your k best sits right at the root, acting as a bouncer. Each new number only has to beat the bouncer to get in; if it does, you evict the bouncer and insert the newcomer.

public static int[] topK(int[] stream, int k) {
    MinHeap heap = new MinHeap();
    for (int x : stream) {
        if (heap.size() < k) {
            heap.insert(x);
        } else if (k > 0 && x > heap.peek()) {
            heap.extractMin(); // evict the smallest of the k kept
            heap.insert(x);
        }
    }
    int[] result = new int[heap.size()];
    for (int i = 0; i < result.length; i++) {
        result[i] = heap.extractMin(); // drain the k kept → ascending
    }
    return result;
}

The heap never grows past k, so every element costs O(log k), and the whole scan is O(n log k) with only O(k) memory. On a billion-row log with k = 10, that’s the difference between a heap of ten entries and sorting a billion rows. This is the pattern behind “top 10 trending” on a stream that never fits in RAM.

How fast is this, really?

The heap’s whole pitch is that it refuses to over-order. A fully sorted array answers “what’s the min?” for free too — but it pays through the nose to stay sorted on every insert. Let n be the number of items:

Read the table as a story. The sorted array wins on search because it’s totally ordered — but that same total order is what makes its inserts O(n), since every new value shoves the rest over to keep the line perfect. The heap keeps only the partial order it actually needs (parent-below-children), so it never pays for order it won’t use: O(log n) in, O(log n) out, and the min waiting for free at the top.

That last row is the heap’s honest weakness, and it’s worth saying plainly: a heap is not a search structure. It can’t find, contains-check, or list items in sorted order without dismantling itself. If you catch yourself wanting those, you want a balanced BST or a hash set, not a heap.

The complete implementation

Every piece we built, assembled — an array-backed min-heap plus the top-k helper:

package dev.fiveyear.heap;
 
import java.util.Arrays;
import java.util.NoSuchElementException;
 
public final class MinHeap {
 
    private int[] heap;
    private int size;
 
    public MinHeap() {
        this.heap = new int[16];
        this.size = 0;
    }
 
    /** Builds a heap from an existing array in O(n) — bottom-up heapify. */
    public MinHeap(int[] values) {
        this.heap = Arrays.copyOf(values, Math.max(values.length, 1));
        this.size = values.length;
        for (int i = size / 2 - 1; i >= 0; i--) {
            siftDown(i);
        }
    }
 
    public boolean isEmpty() {
        return size == 0;
    }
 
    public int size() {
        return size;
    }
 
    /** The smallest element, without removing it. O(1). */
    public int peek() {
        if (size == 0) {
            throw new NoSuchElementException("heap is empty");
        }
        return heap[0];
    }
 
    /** Adds a value and restores the heap property. O(log n). */
    public void insert(int value) {
        if (size == heap.length) {
            heap = Arrays.copyOf(heap, heap.length * 2);
        }
        heap[size] = value; // park it in the first empty slot
        siftUp(size);       // ...and let it climb
        size++;
    }
 
    /** Removes and returns the smallest element. O(log n). */
    public int extractMin() {
        if (size == 0) {
            throw new NoSuchElementException("heap is empty");
        }
        int min = heap[0];
        size--;
        heap[0] = heap[size]; // move the last element into the root
        siftDown(0);          // ...and let it sink
        return min;
    }
 
    /** The k largest of the stream, using a size-k min-heap. O(n log k). */
    public static int[] topK(int[] stream, int k) {
        MinHeap heap = new MinHeap();
        for (int x : stream) {
            if (heap.size() < k) {
                heap.insert(x);
            } else if (k > 0 && x > heap.peek()) {
                heap.extractMin();
                heap.insert(x);
            }
        }
        int[] result = new int[heap.size()];
        for (int i = 0; i < result.length; i++) {
            result[i] = heap.extractMin();
        }
        return result;
    }
 
    // Position is the only pointer we need.
    private static int parent(int i) {
        return (i - 1) / 2;
    }
 
    private static int left(int i) {
        return 2 * i + 1;
    }
 
    private static int right(int i) {
        return 2 * i + 2;
    }
 
    // A freshly parked node climbs while it out-ranks its parent.
    private void siftUp(int i) {
        while (i > 0 && heap[i] < heap[parent(i)]) {
            swap(i, parent(i));
            i = parent(i);
        }
    }
 
    // A too-large node sinks, always swapping with its SMALLER child.
    private void siftDown(int i) {
        while (true) {
            int smallest = i;
            int l = left(i);
            int r = right(i);
            if (l < size && heap[l] < heap[smallest]) {
                smallest = l;
            }
            if (r < size && heap[r] < heap[smallest]) {
                smallest = r;
            }
            if (smallest == i) {
                return;
            }
            swap(i, smallest);
            i = smallest;
        }
    }
 
    private void swap(int a, int b) {
        int tmp = heap[a];
        heap[a] = heap[b];
        heap[b] = tmp;
    }
}

And here it is doing the things we drew:

MinHeap pq = new MinHeap();
pq.insert(5);
pq.insert(1);
pq.insert(4);
pq.insert(8);
pq.insert(3);
 
pq.peek();        // 1  — the smallest, in O(1)
pq.extractMin();  // 1
pq.extractMin();  // 3
pq.size();        // 3
 
int[] heavy = MinHeap.topK(new int[] {7, 2, 9, 4, 11, 6, 5}, 3);
// heavy = [7, 9, 11]  — the three largest, ascending

The interview corner

Heaps show up constantly, usually disguised — “find the k-th largest,” “merge these files,” “running median.” The tell is any phrase like next, closest, smallest so far, or top. Spot the disguise and you’ve half-solved it.

Clarifying questions to ask before you write a line:

• Min-heap or max-heap? Which end do you want cheap? (A max-heap is a min-heap with the comparison flipped — or store negated values.)
• Fixed array up front, or a live stream? A fixed array means O(n) heapify; a stream means insert-as-you-go.
• Do I need to change or remove an item already inside the heap (a “decrease-key” or arbitrary delete)? That question decides whether a bare heap is enough or you need a side index.

The follow-up ladder — where interviewers actually take it:

1. “Find the k-th largest element in a stream.” Keep a size-k min-heap; its root is the k-th largest at all times. O(n log k) time, O(k) space.
2. “Now the running median of a stream.” Two heaps facing each other: a max-heap holding the smaller half, a min-heap holding the larger half. Keep their sizes within one; the median is a root (or the average of the two roots). Each update is O(log n).
3. “Merge k sorted lists into one.” Put the head of each list in a min-heap; repeatedly pop the smallest and push the next element from that list. O(N log k) for N total items — this is the merge step of external sort.
4. “In Dijkstra, a node’s best distance keeps improving — how do you update its priority?” Either support decrease-key with a value → index map so you can find the node and sift it up, or skip all that and use lazy deletion: push a fresh, smaller entry and ignore the stale one when it surfaces. (The Dijkstra article walks through exactly this.)
5. “Delete or reprioritise an arbitrary element.” Locate it via the index map, overwrite it with the last element, shrink — then sift up or down, because the replacement could be smaller or larger than what it replaced. You genuinely need both directions here.

Three mistakes that fail the round:

• Sifting down toward the wrong child. Swapping with the first child that beats the parent, instead of the smaller of the two, corrupts the heap on the first trio where the right child wins. Say “smaller child” and mean it.
• Claiming heapify is O(n log n). It’s O(n), and being able to explain the bottom-heavy sum (most nodes are leaves that barely move) is a green flag interviewers look for.
• Treating a heap like a sorted list. A heap is only partially ordered. Iterating it does not yield sorted order, and searching for an arbitrary element is O(n). Reach for a heap when you touch only the top — never to search the middle.

Where to go from here

You now own the core: a complete tree flattened into an array, kept in order by climbing on insert and sinking on removal. Three natural next stops:

• d-ary heaps. Give each node d children instead of 2 and the tree gets shallower, so sift-up (and thus insert/decrease-key) gets cheaper while sift-down gets a bit dearer. A 4-ary heap is a common, cache-friendly speed-up for Dijkstra, where inserts dominate.
• Fibonacci and pairing heaps. These push decrease-key down to O(1) amortised, which is what makes Dijkstra’s textbook O(E + V log V) bound possible — though their constant factors mean a plain binary heap usually wins in the real world.
• Heapsort. Heapify in O(n), then call extractMin n times, and you’ve sorted in O(n log n) with O(1) extra space — an in-place sort that’s just this article run to completion.

Next time a chest-pain patient walks past a full waiting room, you’ll know the shape of what just happened: a value dropped in at the bottom and climbed, in a handful of swaps, straight to the top of a tree that lives inside an array.