Coding · Heap (priority queue)
Understanding the problem
The question that keeps being asked
A scheduler holds jobs with priorities. Jobs keep arriving, and whenever a worker is free it must take the most urgent job waiting. There are two obvious designs:
- An unsorted list. Adding a job is O(1), but finding the most urgent means scanning everything: O(n) per request.
- A sorted list. The most urgent job is at the front, but every arrival has to be inserted in the right place, shifting what comes after it: O(n) per arrival.
Either way one of the two operations is linear, and over a million arrivals and requests that is around a trillion steps.
| Structure | Add a job | Take the most urgent | 10⁶ of each |
|---|---|---|---|
| Unsorted list | O(1) | O(n) | ≈ 5 × 10¹¹ steps |
| Sorted list | O(n) | O(1) | ≈ 5 × 10¹¹ steps |
| Binary heap | O(log n) | O(log n) | ≈ 4 × 10⁷ steps |
Half-sorted is enough
A heap keeps just enough order to answer the one question. It is a binary tree, stored in an
array, where every parent is no larger than its children. The minimum is always the root,
heap[0]. Nothing is promised about siblings or cousins, and that slack is what makes
updates cheap.
In the array, the children of index i sit at 2i + 1 and 2i + 2, and its parent at (i − 1) / 2, rounded down. There are no pointers to maintain.
- Push: put the new value at the end, then swap it with its parent while it is smaller. It rises at most one level per swap, and the tree has log₂ n levels.
- Pop: take the root, move the last element into its place, then swap it with its smaller child while it is larger. Again at most log₂ n swaps.
Pushes and pops on a min-heap, shown as the array it is stored in. The smallest value is always at index 0.
-
Step 1 / 8heap array70min7size1
Push 7 at the end, then let it rise while it is smaller than its parent (no swaps needed).
-
Step 2 / 8heap array3071min3size2
Push 3 at the end, then let it rise while it is smaller than its parent: 3↔7.
-
Step 3 / 8heap array307192min3size3
Push 9 at the end, then let it rise while it is smaller than its parent (no swaps needed).
-
Step 4 / 8heap array10319273min1size4
Push 1 at the end, then let it rise while it is smaller than its parent: 1↔7, 1↔3.
-
Step 5 / 8heap array1031927354min1size5
Push 5 at the end, then let it rise while it is smaller than its parent (no swaps needed).
-
Step 6 / 8heap array30519273popped1size4
Pop the minimum, 1. The last element, 5, moves to the root and sinks: 5↔3.
-
Step 7 / 8heap array3041927354min3size5
Push 4 at the end, then let it rise while it is smaller than its parent: 4↔5.
-
Step 8 / 8heap array40519273popped3size4
Pop the minimum, 3. The last element, 5, moves to the root and sinks: 5↔4.
Two patterns that cover most questions
Keep k. To find the k largest of n values, keep a min-heap of size k: a new value that beats the root replaces it. The root is always the k-th largest seen so far. O(n log k) time and O(k) memory, and it works on a stream you cannot store.
Take the best available. When options become available over time, push each as it appears and pop the best whenever you choose. Dijkstra's shortest paths, Huffman codes, merging k sorted lists and most scheduling problems are this loop with a different key.
A heap is not a sorted list. Iterating over the array does not give sorted order; only repeated pops do, and n pops cost O(n log n), which is heapsort.