The heap

Start here: what this lesson is for

A heap is the answer to a question that sounds like it needs sorting but does not: what is the smallest thing right now?, asked repeatedly while new items keep arriving.

Sorting answers that, and charges you n log n to put everything in order when you only ever look at one end. A heap does exactly as much work as the question requires and no more - which makes it a good lesson in fitting the structure to the question rather than reaching for the familiar one.

It is also the most physically interesting structure in the course: a tree with no references at all, living inside a flat array, with arithmetic standing in for pointers.

Sorting is more than you needed

You want the smallest item, repeatedly, while new items keep arriving. Sorting gives you that - and charges n log n to put everything in order when you only ever look at one end.

A heap does exactly as much work as the question requires. It keeps one promise and no more: every node is smaller than its children. That's the heap property, and notice what it does not say - it says nothing about left versus right, and nothing about ordering between siblings.

Because the promise is weak, it's cheap to maintain. And because it's applied at every level, the smallest element in the entire structure has nowhere to hide: it must be at the root. Reading the minimum is O(1).

A tree with no references

Here's the part that makes heaps fast in a way Big-O doesn't show. A heap is a complete binary tree - every level full except possibly the last, which fills left to right - and a complete tree can be stored in a plain array, with no node objects and no references at all.

Index arithmetic replaces the pointers. The children of index i live at 2i + 1 and 2i + 2; the parent lives at (i - 1) / 2. Walking the tree becomes multiplication.

Chapter 6 warned that scattered nodes cost cache misses. A heap has none of that - it is one contiguous block, so the constant factor is excellent on top of the good asymptotics. It is a tree with a linked list's flexibility and an array's memory behaviour.

int parent(int i) { return (i - 1) / 2; }
int left(int i)   { return 2 * i + 1; }
int right(int i)  { return 2 * i + 2; }

//        1(0)
//       /    \
//    3(1)    2(2)
//    /  \    /
//  7(3) 4(4) 5(5)

array:  [1, 3, 2, 7, 4, 5]
index:   0  1  2  3  4  5

left(1)  = 3  -> value 7
right(1) = 4  -> value 4
parent(4)= 1  -> value 3

no Node objects, no references, one contiguous block

Sift up, sift down

Two operations maintain the promise, and both are just 'swap with a neighbour until the promise holds again'.

Insert: put the new value at the end of the array - the only spot that keeps the tree complete - then sift up, swapping with its parent while it's smaller. It rises to its level and stops.

Remove the minimum: the root leaves, and to keep the tree complete you move the last element into the root. It's almost certainly too big, so sift down, swapping with its smaller child until the promise holds.

Both walk one root-to-leaf path, and a complete tree's height is log n. That's the O(log n), and the swaps are adjacent array writes, which is why heaps are quick in practice too.

void insert(int value) {
    heap.add(value);                       // end of the array keeps it complete
    int i = heap.size() - 1;
    while (i > 0 && heap.get(i) < heap.get(parent(i))) {
        swap(i, parent(i));                // sift up
        i = parent(i);
    }
}

int removeMin() {
    int min = heap.get(0);
    heap.set(0, heap.remove(heap.size() - 1));   // last element to the root
    int i = 0;
    while (true) {                          // sift down
        int smallest = i;
        if (left(i)  < heap.size() && heap.get(left(i))  < heap.get(smallest)) smallest = left(i);
        if (right(i) < heap.size() && heap.get(right(i)) < heap.get(smallest)) smallest = right(i);
        if (smallest == i) return min;      // promise restored
        swap(i, smallest);
        i = smallest;
    }
}

insert 1 into [3, 4, 8, 9, 5]
  append   [3,4,8,9,5,1]
  sift up  1 < 8  -> [3,4,1,9,5,8]
  sift up  1 < 3  -> [1,4,3,9,5,8]     2 swaps, height 3

removeMin -> 1
  move last to root  [8,4,3,9,5]
  sift down 8 > 3    [3,4,8,9,5]       promise holds

Building a heap from scratch, cheaply

Suppose you already have an array and want it to become a heap. The obvious way is to insert every element one at a time, which costs O(log n) each and O(n log n) overall - the same as sorting, which rather defeats the point.

There is a better way, and it is delightfully counter-intuitive. Start at the last non-leaf node and sift down, working backwards to the root. That is O(n) - building a heap is cheaper than sorting.

The reason is that most nodes are near the bottom, where sifting down has almost nowhere to go. Half the nodes are leaves and need no work at all; a quarter can fall at most one level; only the root can fall the full log n. Sum that series and it converges to about 2n.

This is why heapsort exists: build a heap in O(n), then remove the minimum n times at O(log n) each. Guaranteed O(n log n), in place, with no bad input - the guarantee quicksort could not give you in chapter 4.

void buildHeap(int[] a) {
    // start at the last node that HAS a child and work backwards
    for (int i = a.length / 2 - 1; i >= 0; i--) {
        siftDown(a, i, a.length);
    }
}

n = 1,000,000

insert one at a time   ~20,000,000 operations   O(n log n)
buildHeap (sift down)   ~2,000,000 operations   O(n)

why: how far each node can actually fall
  500,000 leaves        0 levels   ->        0
  250,000 nodes         1 level    ->  250,000
  125,000 nodes         2 levels   ->  250,000
  ...
        1 root         20 levels   ->       20
                                     ~1,000,000 total

Recap: partial order, on purpose

A heap keeps exactly one promise - every node is smaller than its children - and refuses to pay for anything more. That refusal is the entire design.

Because the promise applies at every level, the minimum has nowhere to hide: it must be at the root, so peeking is O(1). Because the promise is weak, restoring it after a change means walking one root-to-leaf path, so insert and remove are O(log n).

Because a heap is a complete tree, its shape is implied by its length, so it lives in a flat array with children at 2i+1 and 2i+2 - no node objects, no references, and excellent cache behaviour on top of good asymptotics.

The one thing to carry away as a warning: iterating a PriorityQueue does not give sorted order. The heap was never fully sorted. Only repeated poll() gives you order, and this catches nearly everyone once.