Heaps and priority queues

Introduction

A priority queue always serves the most important item first: the patient in the most danger, the task with the earliest deadline. A binary heap does this with O(log n) push and pop.

A min-heap is a binary tree where every parent is smaller than or equal to its children, so the smallest item is at the root. The tree is always complete: every level is full except the last, which fills from the left. That shape lets the tree live in a plain array, with no pointers:

A queue serves whoever came first, but real work has priorities. A hospital sees the most urgent patient, and a computer runs the task with the earliest deadline. A heap finds that item quickly, with nothing more than an array.

How it works

Building a heap from an array

#include <stdio.h>

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void sift_down(int a[], int n, int i) {
    while (1) {
        int largest = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < n && a[l] > a[largest]) largest = l;
        if (r < n && a[r] > a[largest]) largest = r;
        if (largest == i) return;
        swap(&a[i], &a[largest]);
        i = largest;
    }
}

int main(void) {
    int a[] = {3, 9, 2, 1, 4, 5};
    int n = 6;
    for (int i = n / 2 - 1; i >= 0; i--) sift_down(a, n, i);
    for (int i = 0; i < n; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

This one is a max-heap (parents larger). Pushing n items one by one costs O(n log n), but there is a faster way: sift down every node that has children, from the last of them (n/2 - 1) back to the root. Most nodes are near the bottom and move only a little, so the total is O(n).

Syntax

// for the item at index i, in an array that starts at 0
int parent = (i - 1) / 2;
int left   = 2 * i + 1;
int right  = 2 * i + 2;

Example

#include <stdio.h>
#define CAPACITY 10

int heap[CAPACITY];
int size = 0;

void swap(int *a, int *b) {
    int t = *a;
    *a = *b;
    *b = t;
}

void push(int x) {
    int i = size++;
    heap[i] = x;
    while (i > 0 && heap[(i - 1) / 2] > heap[i]) {   // smaller than its parent: move up
        swap(&heap[(i - 1) / 2], &heap[i]);
        i = (i - 1) / 2;
    }
}

int pop(void) {
    int top = heap[0];
    heap[0] = heap[--size];
    int i = 0;
    while (1) {
        int l = 2 * i + 1, r = 2 * i + 2, smallest = i;
        if (l < size && heap[l] < heap[smallest]) smallest = l;
        if (r < size && heap[r] < heap[smallest]) smallest = r;
        if (smallest == i) break;
        swap(&heap[i], &heap[smallest]);
        i = smallest;
    }
    return top;
}

int main(void) {
    int values[] = {40, 10, 30, 5, 20};
    for (int k = 0; k < 5; k++) push(values[k]);
    while (size > 0) printf("%d ", pop());
    printf("\n");
    return 0;
}

• push: put the new item at the end of the array (the next free place in the tree), then sift up: while it is smaller than its parent, swap them.
• pop: the answer is heap[0]. Move the last item to the root, then sift down: while it is bigger than its smaller child, swap with that child.

Each sift walks one path between the root and a leaf, and a complete tree has height about log₂ n, so both are O(log n). Popping everything gives the items in sorted order; that is heap sort, in the Algorithms course.

Line by line

1. heap is the array, and size is how many items are in use.
2. push stores the new value at the end, then swaps it upward while its parent is larger.
3. pop saves heap[0] and moves the last item to the root.
4. The loop in pop finds the smallest of the node and its two children. If the node is already smallest, it stops.
5. Otherwise it swaps with that child and continues from there.
6. main pushes five values, then pops them all, so they print in increasing order.

Expected result

5 10 20 30 40 

In the real world

Operating systems schedule tasks with priority queues, and route-finding programs use them to pick the nearest unexplored place. Whenever a program repeatedly needs "the smallest so far", a heap is usually the tool.

Common mistakes

• Using 2 * i and 2 * i + 1 for the children: that formula is for arrays starting at index 1.
• In sift-down, comparing with only the left child: swap with the smaller child (larger, for a max-heap), or the order breaks.
• Thinking a heap is sorted: only the root is guaranteed to be the smallest.

Best practices

• Check l < size and r < size before comparing with a child.
• Remember which kind of heap you are writing, and keep every comparison consistent.
• Use an index-based array, unless the items must also be found by name.

Summary

A binary heap is a complete tree stored in an array, with each parent no larger than its children. Sift-up and sift-down keep that true in O(log n), and the smallest item is always at index 0.

Mark lesson complete