Binary heaps

What if a priority queue were a tree kept in an array? Watch each new job climb one path, never the whole array.

⋯26bool heap_push(struct heap *h, struct job j)27{28    if (h->size == CAP)29        return false;30    int i = h->size;31    h->items[i] = j;32    h->size++;33    while (i > 0) {34        int parent = (i - 1) / 2;35        if (h->items[parent].priority <= h->items[i].priority)36            break;37        swap_jobs(&h->items[parent], &h->items[i]);38        i = parent;39    }40    return true;41}42 43struct job heap_pop(struct heap *h)44{45    struct job top = h->items[0];46    h->size--;47    h->items[0] = h->items[h->size];48    int i = 0;49    for (;;) {50        int l = 2 * i + 1;51        int r = 2 * i + 2;52        int smallest = i;53        if (l < h->size && h->items[l].priority < h->items[smallest].priority)54            smallest = l;55        if (r < h->size && h->items[r].priority < h->items[smallest].priority)56            smallest = r;57        if (smallest == i)58            break;59        swap_jobs(&h->items[i], &h->items[smallest]);60        i = smallest;61    }62    return top;63}⋯70    for (int i = 0; i < 6; i++)71        heap_push(&h, jobs[i]);⋯76    while (h.size > 0) {77        struct job j = heap_pop(&h);78        printf("%d %s\n", j.priority, j.name);

A tree in an array

A binary heap is a complete binary tree, stored in an array exactly as Tree representations stored one: the children of cell i are cells 2i + 1 and 2i + 2, and its parent is cell (i − 1)/2, rounded down. A heap adds one rule, the heap property: every parent is no larger than its children. This is a min-heap; the smallest key is always at the root, cell 0.

The rule says nothing about two children, or about cousins. After the six pushes the array reads 1 3 2 5 9 8: not sorted. Only each parent is checked against its own children, so 3 sits in cell 1 although 2 is smaller. The second smallest key is in cell 1 or cell 2, never further down.

Two operations keep the rule:

• Push. Put the new key in the next free cell, the next position in the tree. If it is smaller than its parent, swap them, and repeat from the parent: the key sifts up until its parent is no larger or it reaches the root.
• Pop. Take the root, the smallest key. Move the last key into the root, then, while it is larger than one of its children, swap it with the smaller child: it sifts down.

The code and its cost

The heap

The full program, jobs.c, stores jobs, each a priority and a name, in a struct on main’s stack:

struct job {
    int priority;
    const char *name;
};

struct heap {
    struct job items[CAP];
    int size;
};

struct heap h = { .size = 0 };

{ .size = 0 } sets size to 0, and every member it does not name starts at zero too, so the 16 items begin as priority 0 and a null name. A struct job is 16 bytes (4 for the priority, 4 of padding, 8 for the pointer), and struct heap is 264.

Push: sift up

int i = h->size;
h->items[i] = j;
h->size++;
while (i > 0) {
    int parent = (i - 1) / 2;
    if (h->items[parent].priority <= h->items[i].priority)
        break;
    swap_jobs(&h->items[parent], &h->items[i]);
    i = parent;
}

heap_push first returns false if all CAP cells are taken. Then the new job goes in cell size, and the loop walks it up while its parent’s priority is larger. swap_jobs swaps two whole jobs, priority and name together, and counts the swap.

Pop: sift down

struct job top = h->items[0];
h->size--;
h->items[0] = h->items[h->size];
int i = 0;
for (;;) {
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    int smallest = i;
    if (l < h->size && h->items[l].priority < h->items[smallest].priority)
        smallest = l;
    if (r < h->size && h->items[r].priority < h->items[smallest].priority)
        smallest = r;
    if (smallest == i)
        break;
    swap_jobs(&h->items[i], &h->items[smallest]);
    i = smallest;
}
return top;

smallest ends at whichever of the three cells, i and its two children, holds the smallest priority; the checks l < h->size and r < h->size skip children that are past the end. If i is already the smallest, the key is in place. heap_pop reads cell 0 without checking, so it must only be called when size > 0; main’s loop checks that first.

What it costs

A complete tree of n keys has height ⌊log₂ n⌋. A push swaps at most once per level on the way up, and a pop at most once per level on the way down, so each costs O(log n). Looking at the smallest key without removing it is O(1): it is h->items[0]. With more children per node the tree is shallower, which d-ary heaps trade against dearer pops.

Changing a priority

A scheduler sometimes needs to make a waiting job more or less urgent. That is a sift up or a sift down from the job’s cell, but the heap does not know where a job is. The usual answer is a second array, from each job to its current cell, updated inside every swap; then a priority can change in O(log n).

A max-heap

Reverse every comparison (>= for <= in the push, > for < in the pop) and the largest key rises to the root instead: a max-heap.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic jobs.c -o jobs
./jobs

It prints heap: 1 3 2 5 9 8, 4 swaps, then the jobs in order of priority: 1 alarm, 2 payroll, 3 email, 5 backup, 8 report, 9 cleanup.

Worked example

Pop by hand from 1 3 2 5 9 8. 1 is the answer. The last key, 8, moves to cell 0. Its children are 3 (cell 1) and 2 (cell 2); 2 is smaller and smaller than 8, so they swap. 8 is now in cell 2, whose children would be cells 5 and 6, past the end of a heap of 5. The array is 2 3 8 5 9, as at the end of the clip.

Push 0 into 1 3 2 5 9 8. 0 lands in cell 6, whose parent is cell 2, holding 2: swap. Now in cell 2, its parent is cell 0, holding 1: swap again. The array is 0 3 1 5 9 8 2, after 2 swaps.

A million jobs. The tree has height ⌊log₂ 1,000,000⌋ = 19, so a push or a pop makes at most 19 swaps.

Two checks. Is 1 2 3 4 5 a min-heap? (Yes: 1 is above 2 and 3, and 2 is above 4 and 5.) Is 1 3 2 2 9? (No: cell 3 holds 2, under cell 1’s 3.) And where is the largest key of a min-heap? (In a leaf: the back half of the array.)

Where it’s used

Priority queues. A heap is the usual way to build one: task schedulers that run the most urgent job next, and event simulations that always take the earliest event.

Shortest paths. Dijkstra’s algorithm (19.5) keeps the places still to visit in a min-heap, ordered by distance.

Merging and top-k. Merging many sorted files keeps one item per file in a heap; keeping the k largest values of a stream keeps them in a min-heap of size k and drops the smallest whenever a larger value arrives.

Sorting. Heapsort builds a heap in the array and pops it into the same array.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.