Heaps & Priority Queues: guided lesson

the story

Binary heap: sift up and sift down

Every tool here exists because something was too slow or broke without it. Here is what.

1964 · J. W. J. Williams

The binary heap arrived in June 1964, inside J. W. J. Williams's Algorithm 232: Heapsort in Communications of the ACM. It keeps a tree in a plain array with a single rule — every parent ≤ its children — so the minimum is always the first element (A[1] in his ALGOL, index 0 in Java). The Java Toolkit chapter's PriorityQueue card tells how this structure became java.util.PriorityQueue in Java 5. This card is about the two moves that make it work: sift up and sift down.

the problem it solved

Taking the smallest item again and again while new items keep arriving — O(log n) per step instead of re-sorting everything.

why it matters: without it

"Give me the next most urgent item" would mean a full scan or a re-sort on every call — O(n) or O(n log n) instead of O(log n).

sources: J. W. J. Williams, Algorithm 232: Heapsort, Communications of the ACM 7(6), 1964 ↗ · OpenJDK 17 source: java.util.PriorityQueue ("represented as a balanced binary heap") ↗

also in this chapter: Building a heap in O(n) (Floyd's heapify) · Heapsort · Top-k with a size-k heap · Two heaps for a running median · K-way merge with a min-heap · Greedy with a heap

the idea

The idea in 30 seconds

A heap is a complete binary tree where every parent is ≤ its children (min-heap). So the minimum is always on top.

It isn't fully sorted — only parent vs child is ordered. That weaker promise is what makes insert and remove-min cheap: O(log n).

It lives in a plain array: the children of index i are 2i+1 and 2i+2, the parent is (i−1)/2. Java's PriorityQueue is exactly this.

picture this

Think of the scheduler behind Task Manager: dozens of processes are waiting, and the CPU always picks the most urgent one next. When a new process arrives, it is slotted in with a few comparisons — nobody re-sorts the whole waiting list.

watch it

offer — append and sift up

Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.

sim

offer — append and sift up

Tree and array are the same data. Watch a value bubble up while it's smaller than its parent at (i−1)/2.

loading simulation…

javajava.util.*

1/** A binary min-heap of ints stored in an array: children of i are 2i+1 and 2i+2, parent is (i-1)/2. */2class MinHeap {3    private int[] a = new int[16];4    private int size = 0;5 6    void offer(int x) {7        if (size == a.length) a = Arrays.copyOf(a, size * 2);   // grow like ArrayList8        a[size] = x;                                   // new value goes in the next free slot9        siftUp(size++);10    }11 12    private void siftUp(int i) {13        while (i > 0) {14            int parent = (i - 1) / 2;15            if (a[parent] <= a[i]) break;              // order holds: stop16            swap(i, parent);                           // smaller value bubbles up17            i = parent;18        }19    }20 21    int peek() {22        if (size == 0) throw new NoSuchElementException();23        return a[0];                                   // the minimum is always the root24    }25 26    int poll() {27        if (size == 0) throw new NoSuchElementException();28        int top = a[0];29        a[0] = a[--size];                              // last leaf jumps to the root30        siftDown(0);31        return top;32    }33 34    private void siftDown(int i) {35        while (true) {36            int left = 2 * i + 1, right = left + 1, smallest = i;37            if (left < size && a[left] < a[smallest]) smallest = left;38            if (right < size && a[right] < a[smallest]) smallest = right;39            if (smallest == i) return;                 // both children are bigger: stop40            swap(i, smallest);                         // larger value sinks41            i = smallest;42        }43    }44 45    /** Floyd's build-heap: sift down every parent, last parent first. O(n), not O(n log n). */46    static MinHeap heapify(int[] values) {47        MinHeap h = new MinHeap();48        h.a = Arrays.copyOf(values, Math.max(16, values.length));49        h.size = values.length;50        for (int i = h.size / 2 - 1; i >= 0; i--) h.siftDown(i);   // leaves are already heaps51        return h;52    }53 54    int size() {55        return size;56    }57 58    private void swap(int i, int j) {59        int t = a[i];60        a[i] = a[j];61        a[j] = t;62    }63}

On this screen ← / → step the simulation. Use the buttons below to move through the lesson.

watch it

poll — take the root, sift down

Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.

sim

poll — take the root, sift down

The last leaf jumps to the root to keep the tree complete, then sinks past the smaller child.

loading simulation…

javajava.util.*

1/** A binary min-heap of ints stored in an array: children of i are 2i+1 and 2i+2, parent is (i-1)/2. */2class MinHeap {3    private int[] a = new int[16];4    private int size = 0;5 6    void offer(int x) {7        if (size == a.length) a = Arrays.copyOf(a, size * 2);   // grow like ArrayList8        a[size] = x;                                   // new value goes in the next free slot9        siftUp(size++);10    }11 12    private void siftUp(int i) {13        while (i > 0) {14            int parent = (i - 1) / 2;15            if (a[parent] <= a[i]) break;              // order holds: stop16            swap(i, parent);                           // smaller value bubbles up17            i = parent;18        }19    }20 21    int peek() {22        if (size == 0) throw new NoSuchElementException();23        return a[0];                                   // the minimum is always the root24    }25 26    int poll() {27        if (size == 0) throw new NoSuchElementException();28        int top = a[0];29        a[0] = a[--size];                              // last leaf jumps to the root30        siftDown(0);31        return top;32    }33 34    private void siftDown(int i) {35        while (true) {36            int left = 2 * i + 1, right = left + 1, smallest = i;37            if (left < size && a[left] < a[smallest]) smallest = left;38            if (right < size && a[right] < a[smallest]) smallest = right;39            if (smallest == i) return;                 // both children are bigger: stop40            swap(i, smallest);                         // larger value sinks41            i = smallest;42        }43    }44 45    /** Floyd's build-heap: sift down every parent, last parent first. O(n), not O(n log n). */46    static MinHeap heapify(int[] values) {47        MinHeap h = new MinHeap();48        h.a = Arrays.copyOf(values, Math.max(16, values.length));49        h.size = values.length;50        for (int i = h.size / 2 - 1; i >= 0; i--) h.siftDown(i);   // leaves are already heaps51        return h;52    }53 54    int size() {55        return size;56    }57 58    private void swap(int i, int j) {59        int t = a[i];60        a[i] = a[j];61        a[j] = t;62    }63}

On this screen ← / → step the simulation. Use the buttons below to move through the lesson.

key idea 1 of 9