Heap sort

Why it exists

Merge sort guarantees $n \log n$ but needs a second array; quicksort is in place and fast but can degrade to $n^2$. Heap sort gets both guarantees at once: in place and $\Theta(n \log n)$ in the worst case. It is the sort to name when an exam asks for "in place with guaranteed $O(n \log n)$". The price is a larger constant than quicksort and no stability.

Prerequisites

The structure and its operations (sift up, sift down, build) are in binary heaps and heap applications. This page adds the analysis as a sorting algorithm and the comparison with the other sorts.

Precise definitions

Max-heap. An array $a[1..n]$ in which $a[i] \ge a[2i]$ and $a[i] \ge a[2i + 1]$ whenever those positions exist; the maximum is $a[1]$.

Sift down at position $i$: while a child is larger than $a[i]$, swap $a[i]$ with the larger child and move down. It costs at most two comparisons per level.

Heap sort. (1) Build: for $i = \lfloor n/2 \rfloor, \ldots, 1$ sift down position $i$ (the leaves are already heaps). (2) Extract: for $e = n, n - 1, \ldots, 2$: swap $a[1]$ and $a[e]$ (the maximum goes to its final place) and sift down position $1$ in the heap $a[1..e-1]$. The array ends in increasing order.

How it works

The two animations below are real runs of the C code (the same functions that are used on the heap pages): first the bottom-up build, then the whole sort. In the second, green cells are in their final places.

Cost of building. A node of height $h$ (the longest path down to a leaf) is sifted down at most $h$ levels, two comparisons per level. A heap of $n$ nodes has at most $\lceil n / 2^{h+1} \rceil$ nodes of height $h$, so the total number of comparisons is about

More precisely the sum of the heights of all nodes is $n - (\text{number of 1 bits of } n)$, so building uses at most $2(n - \text{popcount}(n))$ comparisons, less than $2n$: building is $\Theta(n)$, not $n \log n$. Inserting the keys one by one (sift up) has a worst case of $\Theta(n \log n)$.

Cost of extracting. There are $n - 1$ extractions. Each sifts the new root down at most $\lfloor \log_2 n \rfloor$ levels, two comparisons per level: at most $2 \lfloor \log_2 n \rfloor$ comparisons each, so at most $2 n \lfloor \log_2 n \rfloor$ in all. The extraction phase must be $\Omega(n \log n)$ in the worst case: heap sort is a comparison sort, which needs $\Omega(n \log n)$ comparisons (lower bound), and the build takes only $O(n)$. In practice the key moved to the root is a former leaf and sinks almost to the bottom.

Total. $\Theta(n)$ for the build plus $\Theta(n \log n)$ for the extractions: $\Theta(n \log n)$ in the best, average and worst case; space $O(1)$ extra. (If all keys are equal and the sift down uses a strict comparison it stops at once and the sort is linear; the usual statement for exams is $\Theta(n \log n)$ for all cases.)

Measured. The program counts the comparisons of keys in the build (bottom-up and by repeated insertion) and of the complete sort, on a random input for $n = 15, 63, 255, 1023$.

#include <stdio.h>
 
static long cmps;
 
static void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; }
 
/* a[1..n]: the subtree at i is made a max-heap, given that both subtrees below it already are */
static void sift_down(int a[], int n, int i) {
    for (;;) {
        int l = 2 * i, r = l + 1, big = i;
        if (l <= n) { cmps++; if (a[l] > a[big]) big = l; }
        if (r <= n) { cmps++; if (a[r] > a[big]) big = r; }
        if (big == i) return;
        swap(&a[i], &a[big]);
        i = big;
    }
}
 
static void sift_up(int a[], int i) {
    while (i > 1) {
        cmps++;
        if (a[i / 2] >= a[i]) return;
        swap(&a[i / 2], &a[i]);
        i /= 2;
    }
}
 
static long by_build(int a[], int n) {            /* bottom-up: sift down from n/2 to 1 */
    cmps = 0;
    for (int i = n / 2; i >= 1; i--) sift_down(a, n, i);
    return cmps;
}
 
static long by_insert(int a[], int n) {           /* n insertions, each sifted up */
    cmps = 0;
    for (int i = 2; i <= n; i++) sift_up(a, i);
    return cmps;
}
 
static long sort_all(int a[], int n) {            /* heap sort: build, then n - 1 extractions */
    by_build(a, n);
    for (int e = n; e > 1; e--) { swap(&a[1], &a[e]); sift_down(a, e - 1, 1); }
    for (int i = 2; i <= n; i++) if (a[i - 1] > a[i]) return -1;
    return cmps;
}
 
int main(void) {
    static int a[1100], b[1100];
    int ns[] = {15, 63, 255, 1023};
    unsigned s = 4242;
    printf("%5s %8s %8s %9s\n", "n", "build", "insert", "heapsort");
    for (int q = 0; q < 4; q++) {
        int n = ns[q];
        for (int i = 1; i <= n; i++) { a[i] = i; }
        for (int i = n; i > 1; i--) { s = s * 1103515245u + 12345u; int j = 1 + (int)((s >> 8) % (unsigned)i); swap(&a[i], &a[j]); }
        for (int i = 1; i <= n; i++) b[i] = a[i];
        long cb = by_build(a, n);
        for (int i = 1; i <= n; i++) a[i] = b[i];
        long ci = by_insert(a, n);
        for (int i = 1; i <= n; i++) a[i] = b[i];
        long cs = sort_all(a, n);
        printf("%5d %8ld %8ld %9ld\n", n, cb, ci, cs);
    }
    return 0;
}

    n    build   insert  heapsort
   15       22       21        76
   63      112      127       564
  255      472      551      3281
 1023     1890     2323     17292

Bottom-up building stayed below $2$ comparisons per key. (In this single run repeated insertion was cheaper for the smallest input and dearer for the larger ones; its guaranteed worst case is $\Theta(n \log n)$, while bottom-up is guaranteed linear.) The whole sort used between $1.3$ and $1.7$ times $n \log_2 n$ comparisons, rising with $n$ and never above the bound $2 n \log_2 n$; for the larger $n$ that is more than the $1.39\, n \log_2 n$ average of quicksort (quicksort) and than merge sort's $n \log_2 n$ (merge sort).

Properties.

• In place: only a few variables besides the array.
• Not stable: the root is swapped with the last leaf, a long jump that ignores equal keys (the measured test of stability and comparison of sorts shows $3149$ of $3279$ small arrays reordered).
• Not adaptive: already sorted input costs the same as random input.
• Cache behaviour: the parent and children are far apart in memory, so heap sort is slower in practice than merge sort or quicksort, which scan memory sequentially.
• A max-heap produces increasing order. Using a min-heap and writing the extracted keys to a new array (or to the end of a reversed array) gives decreasing order.

Heaps for partial answers. The $k$ largest of $n$ keys: build a max-heap and extract $k$ times, $\Theta(n + k \log n)$; or keep a min-heap of the $k$ largest seen so far, $\Theta(n \log k)$. Both beat sorting when $k$ is small.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The structure is in binary heaps and its uses in heap applications, where the same two animations appear. The comparison with the other sorts is in stability and comparison of sorts; the competing methods are merge sort and quicksort. Priority queues built on heaps drive Dijkstra's algorithm and Huffman coding.

PYQs

Consider a complete binary tree where the left and
the right subtrees of the root are max heaps. The
lower bound for the number of operations to
convert the tree to a heap is

Match the algorithms with their time complexities:
Algorithm
Time
complexity
P Towers of Hanoi with
n disks
i
Θ(n2 )
Q Binary search given n
sorted numbers
ii
Θ(nlog n)
R Heap sort given n
numbers at the worst
case
iii
Θ(2n )
S
Addition of two n × n
matrices
iv
Θ(logn)
ALGORITHMS

Check Out Our Gate Courses & Secure Your Dream Rank !

The number of elements that can be sorted in
Θ(log n) time using heap sort is

Self-check

Revision card

References