A heap always knows its largest key. Watch it hand that key to the end of the array, again and again, until all are sorted.
Sorting with a heap
Eight numbers made into a heap, then sorted from the back
static void sift_down(int *a, int n, int i){ for (;;) { int l = 2 * i + 1; int r = 2 * i + 2; int largest = i; 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; }} void heapify(int *a, int n){ for (int i = n / 2 - 1; i >= 0; i--) sift_down(a, n, i);} void sort_heap(int *a, int n){ for (int end = n - 1; end > 0; end--) { swap(&a[0], &a[end]); sift_down(a, end, 0); }} int a[N] = { 3, 9, 2, 1, 7, 5, 8, 4 }; heapify(a, N); print("heap", a, N); swaps = 0; sort_heap(a, N); print("sorted", a, N);a holds 3 9 2 1 7 5 8 4.
- phase
- building the heap
- heap size
- 8
- swaps
- 0
Output
Describe this picture
Two pictures side by side, with the code under them. On the left, the heap drawn as a tree: cell 0 at the top, the children of cell i at cells 2i + 1 and 2i + 2, each node labelled with its cell number. On the right, the eight cells of int a[8] as bars, each as tall as its number. A ring marks the key being worked on, in both pictures; cells that have joined the sorted tail are tinted in the done colour and leave the tree. The code pane shows sift_down, heapify, sort_heap and main’s calls, with the line about to run marked. The clip starts from 3 9 2 1 7 5 8 4, about 24 seconds. First the parents light from cell 3 back to cell 0, each sifting down: 1 swaps with 4; 2 swaps with 8; 9 stays; 3 swaps with 9, then with 7. The array is now the max-heap 9 7 8 4 3 5 2 1. Then, seven times, the root swaps with the last cell of the heap, the heap loses that cell, and the new root sifts down until the next largest is on top: 9, 8, 7, 5, 4, 3 and 2 join the tail from the right, and 1 is left in cell 0. The array ends as 1 2 3 4 5 7 8 9. Under the pictures are one sentence on the current step and the readouts “phase”, “heap size” and “swaps”; the swap count starts again at 0 for the sort phase, as the program’s does, and ends at 15. The transport plays and pauses, steps one beat back or forward, and scrubs; a paused step is kept in the page address as heapsort.step.
Two phases in one array
Heapsort uses a max-heap: every parent no smaller than its children, so the largest key is in cell 0. It works in two phases, in the array it is given.
Build the heap. Every leaf is already a heap of one. So go through the parents from the last one, cell n/2 − 1, back to cell 0, and sift each one down into the heap below it. When cell 0 is done, the whole array is a heap.
Sort. The largest key is at the root. Swap it with the last cell of the heap: it is now where it belongs in the sorted array, and the heap is one cell shorter. The key that came to the root is probably too small for it, so sift it down. Repeat until the heap has one cell.
Key idea
The sorted tail grows from the right while the heap shrinks, in the same array.
The code and its cost
Sift down
static void sift_down(int *a, int n, int i)
{
for (;;) {
int l = 2 * i + 1;
int r = 2 * i + 2;
int largest = i;
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;
}
}This is the pop’s sift-down from Binary heaps with every comparison reversed, so the larger child wins. n is the size of the heap, not of the array: cells from n on are left alone.
The two phases
void heapify(int *a, int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
sift_down(a, n, i);
}
void sort_heap(int *a, int n)
{
for (int end = n - 1; end > 0; end--) {
swap(&a[0], &a[end]);
sift_down(a, end, 0);
}
}heapify starts at n / 2 - 1 because that is the last cell with a child; for 8 cells it is cell 3, whose child is cell 7. In sort_heap, end is the last cell of the heap: the root goes there, and sift_down(a, end, 0) restores a heap of end cells.
Why building costs O(n)
Pushing n keys one at a time costs O(n log n) in the worst case. Building from the bottom up is cheaper, because most nodes are near the bottom and can only sift a short way. A node at height k sifts down at most k levels, and about n/2^(k+1) nodes have height k. The total is at most
so building the heap is O(n).
The sort phase and the properties
The sort phase sifts down n − 1 times, each at most ⌊log₂ n⌋ levels: O(n log n). Heapsort therefore takes O(n log n) in every case, with no bad inputs. It sorts in place, with O(1) extra memory: a few variables, no second array and no recursion. It is not stable: equal keys can come out in a different order from the one they went in. In practice it is often slower than quicksort, because its jumps between a node and its children are far apart in memory for large arrays.
Running it yourself
gcc -std=c11 -Wall -Wextra -pedantic heapsort.c -o heapsort
./heapsortIt prints heap: 9 7 8 4 3 5 2 1 (4 swaps), then sorted: 1 2 3 4 5 7 8 9 (15 swaps).
Worked example
Bottom-up against one by one. Take 1 2 3 4 5 6 7 8, sorted the wrong way for a max-heap. heapify makes it a heap in 6 swaps. Pushing the same keys one by one into a max-heap makes 13 swaps, because each new key is the largest so far and climbs all the way to the root: 0 + 1 + 1 + 2 + 2 + 2 + 2 + 3. The program build-compare.c counts both and prints heapify: 6 swaps, then 8 pushes: 13 swaps.
Not stable. Sort three items by key, where two have the key 5: 5a, 5b, 1. Heapify leaves them in place (5a is no smaller than its children). The first swap sends 5a to the end and 1 to the root; 1 sifts down, which brings 5b up to the root, and the next swap puts 5b in the middle. The result is 1, 5b, 5a: the two fives reversed.
Two checks. For n = 10, which parent does heapify visit first? (Cell 4, since 10/2 − 1 = 4; its child is cell 9.) How much extra memory does heapsort need? (O(1).)
Where it’s used
A guaranteed fallback. Library sorts often use introsort (17.6): quicksort that switches to heapsort if its recursion goes too deep, so the worst case stays O(n log n).
Partial sorts. “The 10 largest of a million” is a heap built in O(n) and 10 pops: no need to sort the rest.
Embedded code. Where memory is tight and the worst case must be known in advance, heapsort’s O(1) extra memory and O(n log n) bound are what matter.
Reference card
| Code or idea | Meaning |
|---|---|
| max-heap | every parent ≥ its children; the largest in cell 0 |
heapify | sift down every parent from cell n/2 − 1 back to 0: O(n) |
sort_heap | swap the root to cell end, sift down over end cells, n − 1 times |
| cost | O(n log n) in every case |
| memory | in place, O(1) extra |
| stable | no |
| first parent | cell n/2 − 1 |
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.