On this page

Heap Sort

Heap sort is the only classic comparison sort that is at once in place (constant extra memory), in the worst case, and simple enough to write from memory in a dozen lines. Merge sort has the guarantee but needs a second array; quicksort is in place but has a quadratic worst case. Heap sort has neither weakness, which is why it is the safety net inside introsort, the sort inside the Linux kernel, and the right answer whenever an interviewer says " extra space and a worst-case bound". It is also, on large arrays, usually slower than both of its rivals — and understanding why teaches you more about real hardware than any other sorting algorithm.

Lesson position: Module 2 · Searching & Sorting · previous: Quick Sort, Partition Schemes & Introsort · next: Non-Comparison Sorts & the Lower Bound · course map.

Why this exists

Selection sort has the right idea and the wrong data structure. It repeatedly finds the largest remaining element and moves it to the end — rounds of an scan, total. The scan is wasteful because every round re-learns almost everything the previous round knew. A max-heap remembers: it keeps the elements in a shape where the maximum is always at the front, and removing the maximum and repairing the shape costs instead of . Swap the linear scan for a heap and selection sort becomes heap sort: rounds of .

J. W. J. Williams introduced both the binary heap and heap sort in "Algorithm 232: Heapsort" (Communications of the ACM, 1964). The same year Robert W. Floyd published "Algorithm 245: Treesort 3", which builds the heap bottom-up in linear time rather than by insertions, and that is the version everyone implements today. Floyd also observed that the repair step could use fewer comparisons by first walking all the way to a leaf; Ingo Wegener's 1993 analysis of this bottom-up heapsort showed it uses about comparisons on average, close to the information-theoretic minimum.

Where does heap sort run? Wherever a worst-case bound matters more than average speed. It is the fallback in introsort (C++ std::sort), in Java's dual-pivot quicksort and in pdqsort. The Linux kernel's general-purpose sort() in lib/sort.c is a bottom-up heapsort, chosen explicitly over quicksort for its worst case and its zero extra memory. Embedded and real-time systems, where recursion depth and allocation must be bounded and timing must be predictable, use it for the same reasons. And the heap itself — the data structure heap sort is built from — is the priority queue under schedulers, Dijkstra's algorithm, event simulators and top-k queries, which the Heaps & Priority Queues lesson covers in depth.

Pattern triggers

If the problem says or has…Think of…
"sort in place" and "worst case "Heap sort (or introsort, which falls back to it)
" extra memory", "no recursion", "bounded stack", embedded / kernel / real-timeHeap sort: iterative, no allocation, no recursion
"k largest", "k smallest", "top k" with A heap of size () or heap select — partial heap sort
"sort only the first k elements"std::partial_sort: heapify a prefix, sweep, then sort the heap
"repeatedly take the max / min and do something"The heap, not the sort (Heaps & Priority Queues)
"nearly sorted", "each element at most k from its place"A size- min-heap sweep:
"stable"Not heap sort — merge sort or Timsort
"fastest possible on large arrays in RAM"Not heap sort — introsort / pdqsort; heap sort's cache misses dominate
"merge k sorted lists/files"A min-heap of the k heads (external sorting's merge phase)

Intuition & first principles

A binary max-heap is a complete binary tree in which every node is greater than or equal to its children. "Complete" means every level is full except possibly the last, which is filled from the left. Two consequences follow from those two properties, and heap sort uses both:

  1. The maximum is at the root. By transitivity, the root is everything.
  2. A complete tree is an array. Number the nodes level by level, left to right, starting at 0. Node 's children are at and ; its parent is at . No pointers, no allocation: any array is a complete binary tree, and the heap property is just an inequality between a[i] and a[2i+1], a[2i+2].
flowchart TD
    N0["index 0: 10"] --> N1["index 1: 5"]
    N0 --> N2["index 2: 8"]
    N1 --> N3["index 3: 4"]
    N1 --> N4["index 4: 1"]
    N2 --> N5["index 5: 3"]

The array [10, 5, 8, 4, 1, 3] drawn as the tree it represents. Every parent is its children, so it is a max-heap. The array view is what lives in memory; the tree view is how you reason.

The single operation everything rests on is sift-down: given a node whose two subtrees are already heaps but which may itself be too small, swap it with its larger child and repeat until it is both children or reaches a leaf. Swapping with the larger child is the essential detail: the larger child becomes the parent of the smaller one, so the heap property holds at the node you just fixed. Sift-down walks one root-to-leaf path, so it costs .

With sift-down, heap sort is two phases:

  1. Heapify. Turn the arbitrary array into a max-heap. Leaves (the second half of the array) are already one-element heaps. Sift down every internal node, from the last one (n // 2 - 1) back to the root. When you reach node , both its subtrees are heaps because their roots have larger indices and were processed already.
  2. Sort. Swap the root (the maximum) with the last element of the heap; that element is now in its final position. Shrink the heap by one and sift the new root down. Repeat until the heap has one element.

The sorted output grows from the right end of the array while the heap shrinks from the left, sharing one array: that is why heap sort needs no extra memory.

flowchart LR
    A["arbitrary array"] -->|"heapify: sift down i = n/2-1 .. 0, O(n)"| B["max-heap a[0..n-1]"]
    B --> C{"heap size > 1 ?"}
    C -->|"yes"| D["swap a[0] with a[end]: max is final"]
    D --> E["heap size -= 1, sift down a[0]: O(log n)"]
    E --> C
    C -->|"no"| F["sorted array"]

Mechanics

Sift-down, heapify and the sort loop

sift_down(a, i, n):                  # heap occupies a[0..n-1]
    while 2i + 1 < n:
        c = 2i + 1                    # left child
        if c + 1 < n and a[c] < a[c + 1]:
            c = c + 1                 # right child is larger
        if a[i] >= a[c]: return       # heap property holds
        swap a[i], a[c]
        i = c

heapsort(a):
    for i = n/2 - 1 down to 0:  sift_down(a, i, n)        # phase 1
    for end = n - 1 down to 1:                              # phase 2
        swap a[0], a[end]
        sift_down(a, 0, end)

Each level of sift-down costs up to two comparisons: one to pick the larger child, one to compare it with the sinking element. That factor of two is the source of heap sort's comparison count, and the target of Floyd's improvement below.

Trace: heap sort of [4, 10, 3, 5, 1, 8]

Computed by script (the visualizer replays the same run). Heap size is the number of elements still in the heap; everything to its right is final.

StepPhaseOperationComparison(s)Array afterHeap size
0startleaves are indices 3..5—[4, 10, 3, 5, 1, 8]6
1heapifysift a[2] = 3: larger child a[5] = 83 < 8 → swap[4, 10, 8, 5, 1, 3]6
2heapifysift a[1] = 10: larger child a[3] = 510 ≥ 5 → stop[4, 10, 8, 5, 1, 3]6
3heapifysift a[0] = 4: larger child a[1] = 104 < 10 → swap[10, 4, 8, 5, 1, 3]6
4heapifycontinue at a[1] = 4: larger child a[3] = 54 < 5 → swap[10, 5, 8, 4, 1, 3]6
5sortswap a[0] ↔ a[5]: 10 is final—[3, 5, 8, 4, 1, 10]5
6sortsift a[0] = 3: larger child a[2] = 83 < 8 → swap[8, 5, 3, 4, 1, 10]5
7sortswap a[0] ↔ a[4]: 8 is final—[1, 5, 3, 4, 8, 10]4
8sortsift a[0] = 1: larger child a[1] = 51 < 5 → swap[5, 1, 3, 4, 8, 10]4
9sortcontinue at a[1] = 1: only child a[3] = 41 < 4 → swap[5, 4, 3, 1, 8, 10]4
10sortswap a[0] ↔ a[3]: 5 is final—[1, 4, 3, 5, 8, 10]3
11sortsift a[0] = 1: larger child a[1] = 41 < 4 → swap[4, 1, 3, 5, 8, 10]3
12sortswap a[0] ↔ a[2]: 4 is final—[3, 1, 4, 5, 8, 10]2
13sortsift a[0] = 3: only child a[1] = 13 ≥ 1 → stop[3, 1, 4, 5, 8, 10]2
14sortswap a[0] ↔ a[1]: 3 is final—[1, 3, 4, 5, 8, 10]1

Heapify used 7 comparisons; the whole sort used 15 (counted by the instrumented implementation below). Notice step 9: when the heap has shrunk to 4 elements, index 4 (holding the already-final 8) is no longer a child of index 1. Getting that boundary wrong — sifting against the full array length instead of the current heap size — is the classic heap sort bug.

Why bottom-up heapify, not n insertions

You could build the heap by inserting elements one at a time with sift-up (append at the end, swap with the parent while larger). That is Williams's original method and costs in the worst case: on ascending input every new element climbs to the root. Floyd's bottom-up heapify costs . The difference is who does the long walks. In sift-up construction, the many nodes near the bottom may each walk the full height. In sift-down construction, nodes near the bottom walk almost nothing — a leaf walks zero levels, its parent at most one — and only the few nodes near the root walk far. Since half the nodes are leaves and a quarter are one level above, the cheap nodes dominate. The Complexity section turns this into a sum.

The ladder: brute force → better → optimal

Rung 1 — selection sort. Find the maximum by linear scan, swap it to the end, repeat. comparisons on every input, space, at most swaps. It is the "selection" skeleton heap sort inherits. See Elementary Sorts.

Rung 2 — priority-queue sort. Push all elements into a separate binary heap (or any priority queue), then pop them in order. time, but extra memory and, with pushes, an build. It improves on rung 1 because each "find max" costs instead of . In Python this is heapq.heapify + heappop into a new list.

Rung 3 — in-place heap sort with bottom-up heapify. Use the input array as the heap, build it in with sift-down, and park each extracted maximum in the slot the heap just vacated. worst case, extra memory, no recursion. About comparisons.

Rung 4 — bottom-up (Floyd/Wegener) heap sort. Same structure, but each sift-down first descends to a leaf along the larger children (one comparison per level), then climbs back up to where the sinking element belongs. Because the element swapped to the root came from the bottom of the heap, it usually belongs near the bottom, so the climb is short. About comparisons on average — half of rung 3. This is what the Linux kernel ships.

RungTime (worst)Comparisons (random input)Extra spaceNotes
Selection sortfewest writes
Priority-queue sort + buildeasiest with a library heap
In-place heap sort (measured at )the textbook version
Bottom-up heap sortthe version in production

Correctness

Lemma 1: sift-down

Claim. If the subtrees rooted at the children of are max-heaps (within the first elements), then after sift_down(a, i, n) the subtree rooted at is a max-heap containing the same elements.

Proof by induction on the height of node . If is a leaf () there is nothing to do. Otherwise let be the larger child. If a[i] >= a[c], then a[i] is both children, which are roots of heaps, so the subtree at is a heap. If a[i] < a[c], swap. Now the new a[i] (old a[c]) is the old a[i] and the other child (because was the larger), and it was everything in its own former subtree. The other child's subtree is untouched and still a heap. The subtree at now has a possibly-too-small root, but its children's subtrees are still heaps, and has height , so by the induction hypothesis the recursive (iterative) continuation makes it a heap. ∎

Lemma 2: heapify

Invariant. At the start of the iteration for index (counting down from ), every node is the root of a max-heap.

  • Initialisation. Nodes are leaves, which are trivial heaps.
  • Maintenance. The children of are and , both , so they are heap roots. Lemma 1 makes a heap root. Nodes outside 's subtree are untouched, and those inside it remain heaps (sift-down only repairs). Decrementing restores the invariant.
  • Termination. At , node 0 is a heap root: the whole array is a max-heap. ∎

Theorem: heap sort sorts

Invariant of the sort loop. At the start of the iteration with heap size (from down to 2):

  1. a[0..m-1] is a max-heap;
  2. a[m..n-1] contains the largest elements of the input, in sorted order;
  3. every element of a[0..m-1] is every element of a[m..n-1].

Initialisation: , the suffix is empty, and Lemma 2 gives (1). Maintenance: a[0] is the maximum of the heap (heap property plus transitivity), and by (3) it is the whole suffix. Swapping it into position extends the sorted suffix with the largest remaining element, preserving (2) and (3). The new root may violate the heap property, but its children are still heap roots within a[0..m-2], so Lemma 1 restores (1) for size . Termination: at , a[1..n-1] holds the largest elements sorted, and a[0] is all of them. The array is sorted. Only swaps were used, so it is a permutation of the input. ∎

The bottom-up variant changes only how sift-down finds the final position of the sinking element; it places the element at the same position as the standard sift-down would for distinct keys, so the same proof applies. (For equal keys it may stop at a different but equally valid position; the heap property still holds.)

Complexity

Heapify is O(n): the summation proof

A heap with nodes has height , and at most nodes of height (CLRS Exercise 6.3-4). Sift-down from a node of height does at most swaps and comparisons. So heapify costs at most

comparisons, using the series

which you get by differentiating to obtain and setting .

There is also an exact form worth knowing: the sum of the heights of all nodes in an -node heap is exactly , where is the number of 1 bits in the binary representation of (we checked this identity for every ). So heapify does at most swaps and at most comparisons. Brute force over all permutations confirms the bound is respected and nearly tight: the worst-case comparison count for is 8, exactly ; for it is 11, against a bound of 14. On random input we measured about comparisons for heapify at .

The intuition from Mechanics is visible in the sum: the terms shrink geometrically, so the cost is dominated by the many short walks near the bottom, not the few long walks near the top.

The sort phase is Θ(n log n)

Each of the extractions sifts down from the root of a heap of size , at most levels and comparisons. Summing, the sort phase does at most comparisons. And it really does walk nearly the full height: the element swapped to the root came from the bottom level, so it is typically one of the smallest elements in the heap and sinks almost all the way back. That is why the average is close to the worst case — our measurement on random doubles:

nHeapify comparisonsTotal (standard)Total / Total (bottom-up)Bottom-up − , per element
1,0241,88717,3221.6910,6170.37
16,38430,842408,3151.78235,1340.35
131,072246,3364,051,6381.822,274,7500.35

The standard version's total is on all three sizes (the ratio creeps toward 2 as grows); bottom-up heapsort's is to . That last constant matches the Linux kernel's own comment in lib/sort.c: "This performs n*log2(n) + 0.37*n + o(n) comparisons on average, and 1.5*n*log2(n) + O(n) in the (very contrived) worst case."

Best, average and worst

  • Worst case: — at most comparisons for the standard version, about for bottom-up (Wegener).
  • Average case: standard, bottom-up.
  • Best case: with all keys equal, every sift stops after one level: (we measured 49,146 comparisons, about , for 16,384 equal keys). With distinct keys the best case is still — already-sorted input does not help (sorted input took comparisons at ; reverse-sorted, which is already a max-heap, took ). Heap sort is not adaptive.
  • Space: extra — a few indices. Iterative, so no stack growth either. This is the strongest space guarantee of any comparison sort in common use.
  • Stability: not stable (next section).

Not stable: a three-element example

Sort the records (2, a), (2, b), (1, c) by their number. Heapify finds the root (2, a) already both children (ties do not swap), so the heap is unchanged. The first extraction swaps the root with the last element: (1, c), (2, b), (2, a) — and (2, a) is now final in the last slot. Sifting (1, c) down swaps it with (2, b), the second extraction puts (2, b) in the middle slot, and the result is [(1, c), (2, b), (2, a)]: the two 2s have swapped order. Even two equal elements [(1, a), (1, b)] come out as [(1, b), (1, a)], because the first extraction always swaps the root with the last element. (Both verified by script.) The long-distance swap from root to end is the culprit, and no tie-breaking rule inside the heap avoids it without storing original indices — which costs space and defeats the point.

Why heap sort is rarely the fastest: the cache

Heap sort and quicksort do a similar number of comparisons (heap sort's bottom-up variant does fewer), yet heap sort usually loses on large arrays. The reason is the memory access pattern. Sift-down at index touches next, then about , then : each level of the walk jumps to a location twice as far into the array. Once the heap is larger than the cache, every level below the cached top of the tree is a likely cache miss, and the hardware prefetcher cannot predict the jumps. Each extraction therefore costs roughly misses, where is the number of elements that fit in cache. Quicksort, by contrast, streams sequentially through memory and recurses into subarrays that soon fit in cache entirely. Heap sort also mispredicts the "which child is larger" branch about half the time, and its swaps form a serial dependency chain down the tree that leaves little room for instruction-level parallelism.

We measured it (MSVC 19, /O2, random 32-bit integers, best of three runs, one machine — treat as an illustration, not a benchmark):

nstd::sortmake_heap + sort_heapSimple heap sort (this page)std::stable_sort
(400 KB)7.6 ms5.1 ms4.3 ms6.6 ms
(4 MB)91 ms72 ms79 ms82 ms
(40 MB)1,103 ms1,931 ms2,977 ms1,016 ms

While the array fits in cache, heap sort is competitive and on this machine even faster than MSVC's std::sort (whose quicksort pays for branch mispredictions on random data). At 40 MB, far beyond the cache, heap sort is 1.75–2.7× slower than introsort and merge sort. The crossover is the cache size, which is precisely the point: asymptotic analysis says the three sorts are equal; the memory hierarchy decides. See Data Structures in Memory and Benchmarks for how to measure this properly.

Known mitigations: a d-ary heap (4 or 8 children per node) makes the tree shallower and puts siblings in one cache line, trading more comparisons per level for fewer levels and misses; cache-aware layouts (LaMarca and Ladner, 1996–1997) group subtrees into cache blocks. Neither has made heap sort the default anywhere — it remains a fallback.

Implementation

The canonical in-place heap sort with bottom-up heapify, plus a helper that checks the heap property. Every block runs the same tests: heapify of the traced array gives [10, 5, 8, 4, 1, 3], the trace's final array, and full sorts of a 2,000-element array with duplicates (MINSTD generator , seed 42, values mod 1000), a sorted, a reversed and an all-equal array, an empty array and a singleton, each compared with the built-in sort.

def sift_down(a: list[int], i: int, n: int) -> None:
    """Restore the max-heap property for the subtree at i, inside a[0..n-1],
    assuming both child subtrees are already heaps."""
    while True:
        c = 2 * i + 1
        if c >= n:
            return
        if c + 1 < n and a[c] < a[c + 1]:
            c += 1                      # larger child
        if a[i] >= a[c]:
            return
        a[i], a[c] = a[c], a[i]
        i = c


def build_max_heap(a: list[int]) -> list[int]:
    """Floyd's bottom-up heapify: O(n)."""
    for i in range(len(a) // 2 - 1, -1, -1):
        sift_down(a, i, len(a))
    return a


def heapsort(a: list[int]) -> list[int]:
    """In-place, O(n log n) worst case, O(1) extra space, not stable."""
    build_max_heap(a)
    for end in range(len(a) - 1, 0, -1):
        a[0], a[end] = a[end], a[0]     # max goes to its final slot
        sift_down(a, 0, end)            # heap is now a[0..end-1]
    return a


def is_max_heap(a: list[int]) -> bool:
    return all(a[(k - 1) // 2] >= a[k] for k in range(1, len(a)))


def minstd(seed: int, n: int, mod: int) -> list[int]:
    out, x = [], seed
    for _ in range(n):
        x = x * 48271 % 2147483647
        out.append(x % mod)
    return out


if __name__ == "__main__":
    assert build_max_heap([4, 10, 3, 5, 1, 8]) == [10, 5, 8, 4, 1, 3]
    assert heapsort([4, 10, 3, 5, 1, 8]) == [1, 3, 4, 5, 8, 10]
    n = 2000
    cases = [minstd(42, n, 1000), list(range(n)), list(range(n, 0, -1)), [7] * n, [], [1]]
    for c in cases:
        assert is_max_heap(build_max_heap(list(c)))
        assert heapsort(list(c)) == sorted(c)
    print("ok")
import java.util.Arrays;

public class HeapSort {
    static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

    /** Restore the max-heap property for the subtree at i, inside a[0..n-1]. */
    static void siftDown(int[] a, int i, int n) {
        while (true) {
            int c = 2 * i + 1;
            if (c >= n) return;
            if (c + 1 < n && a[c] < a[c + 1]) c++;
            if (a[i] >= a[c]) return;
            swap(a, i, c);
            i = c;
        }
    }

    static int[] buildMaxHeap(int[] a) {
        for (int i = a.length / 2 - 1; i >= 0; i--) siftDown(a, i, a.length);
        return a;
    }

    static int[] heapsort(int[] a) {
        buildMaxHeap(a);
        for (int end = a.length - 1; end > 0; end--) {
            swap(a, 0, end);
            siftDown(a, 0, end);
        }
        return a;
    }

    static boolean isMaxHeap(int[] a) {
        for (int k = 1; k < a.length; k++) if (a[(k - 1) / 2] < a[k]) return false;
        return true;
    }

    static int[] minstd(long seed, int n, int mod) {
        int[] out = new int[n];
        long x = seed;
        for (int k = 0; k < n; k++) { x = x * 48271 % 2147483647L; out[k] = (int) (x % mod); }
        return out;
    }

    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    public static void main(String[] args) {
        check(Arrays.equals(buildMaxHeap(new int[] {4, 10, 3, 5, 1, 8}), new int[] {10, 5, 8, 4, 1, 3}), "heapify");
        check(Arrays.equals(heapsort(new int[] {4, 10, 3, 5, 1, 8}), new int[] {1, 3, 4, 5, 8, 10}), "trace");
        int n = 2000;
        int[] srt = new int[n], rev = new int[n], eq = new int[n];
        for (int k = 0; k < n; k++) { srt[k] = k; rev[k] = n - k; eq[k] = 7; }
        for (int[] c : new int[][] {minstd(42, n, 1000), srt, rev, eq, {}, {1}}) {
            check(isMaxHeap(buildMaxHeap(c.clone())), "heap property");
            int[] expect = c.clone();
            Arrays.sort(expect);
            check(Arrays.equals(heapsort(c.clone()), expect), "sorted");
        }
        System.out.println("ok");
    }
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>

// Restore the max-heap property for the subtree at i, inside a[0..n-1].
void siftDown(std::vector<int>& a, std::size_t i, std::size_t n) {
    while (true) {
        std::size_t c = 2 * i + 1;
        if (c >= n) return;
        if (c + 1 < n && a[c] < a[c + 1]) ++c;
        if (a[i] >= a[c]) return;
        std::swap(a[i], a[c]);
        i = c;
    }
}

std::vector<int> buildMaxHeap(std::vector<int> a) {
    for (std::size_t i = a.size() / 2; i-- > 0;) siftDown(a, i, a.size());
    return a;
}

std::vector<int> heapsort(std::vector<int> a) {
    a = buildMaxHeap(std::move(a));
    for (std::size_t end = a.size(); end-- > 1;) {   // end = n-1 .. 1
        std::swap(a[0], a[end]);
        siftDown(a, 0, end);
    }
    return a;
}

bool isMaxHeap(const std::vector<int>& a) {
    for (std::size_t k = 1; k < a.size(); ++k)
        if (a[(k - 1) / 2] < a[k]) return false;
    return true;
}

std::vector<int> minstd(std::uint64_t seed, int n, int mod) {
    std::vector<int> out;
    std::uint64_t x = seed;
    for (int k = 0; k < n; ++k) { x = x * 48271 % 2147483647ULL; out.push_back(static_cast<int>(x % mod)); }
    return out;
}

int main() {
    assert((buildMaxHeap({4, 10, 3, 5, 1, 8}) == std::vector<int>{10, 5, 8, 4, 1, 3}));
    assert((heapsort({4, 10, 3, 5, 1, 8}) == std::vector<int>{1, 3, 4, 5, 8, 10}));
    const int n = 2000;
    std::vector<int> srt(n), rev(n), eq(n, 7);
    for (int k = 0; k < n; ++k) { srt[k] = k; rev[k] = n - k; }
    for (const auto& c : std::vector<std::vector<int>>{minstd(42, n, 1000), srt, rev, eq, {}, {1}}) {
        assert(isMaxHeap(buildMaxHeap(c)));
        auto expect = c;
        std::sort(expect.begin(), expect.end());
        assert(heapsort(c) == expect);
        auto h = buildMaxHeap(c);
        assert(std::is_heap(h.begin(), h.end()));   // agrees with the standard library's definition
    }
    std::cout << "ok\n";
}
function swap(a: number[], i: number, j: number): void {
  const t = a[i]; a[i] = a[j]; a[j] = t;
}

/** Restore the max-heap property for the subtree at i, inside a[0..n-1]. */
function siftDown(a: number[], i: number, n: number): void {
  while (true) {
    let c = 2 * i + 1;
    if (c >= n) return;
    if (c + 1 < n && a[c] < a[c + 1]) c++;
    if (a[i] >= a[c]) return;
    swap(a, i, c);
    i = c;
  }
}

function buildMaxHeap(a: number[]): number[] {
  for (let i = Math.floor(a.length / 2) - 1; i >= 0; i--) siftDown(a, i, a.length);
  return a;
}

function heapsort(a: number[]): number[] {
  buildMaxHeap(a);
  for (let end = a.length - 1; end > 0; end--) {
    swap(a, 0, end);
    siftDown(a, 0, end);
  }
  return a;
}

function isMaxHeap(a: number[]): boolean {
  for (let k = 1; k < a.length; k++) if (a[Math.floor((k - 1) / 2)] < a[k]) return false;
  return true;
}

function minstd(seed: number, n: number, mod: number): number[] {
  const out: number[] = [];
  let x = seed;
  for (let k = 0; k < n; k++) { x = (x * 48271) % 2147483647; out.push(x % mod); }
  return out;
}

function check(ok: boolean, msg: string): void {
  if (!ok) throw new Error("check failed: " + msg);
}
const same = (x: number[], y: number[]) => x.length === y.length && x.every((v, k) => v === y[k]);

check(same(buildMaxHeap([4, 10, 3, 5, 1, 8]), [10, 5, 8, 4, 1, 3]), "heapify");
check(same(heapsort([4, 10, 3, 5, 1, 8]), [1, 3, 4, 5, 8, 10]), "trace");
const n = 2000;
const cases: number[][] = [
  minstd(42, n, 1000),
  Array.from({ length: n }, (_, k) => k),
  Array.from({ length: n }, (_, k) => n - k),
  new Array(n).fill(7),
  [],
  [1],
];
for (const c of cases) {
  check(isMaxHeap(buildMaxHeap([...c])), "heap property");
  check(same(heapsort([...c]), [...c].sort((x, y) => x - y)), "sorted");
}
console.log("ok");

Variant: Floyd's bottom-up sift, with comparison counts

Both versions instrumented to count key comparisons. On the traced array the standard version uses 15 comparisons and the bottom-up version 13; on the 2,000-element MINSTD array (seed 42, values mod ) the standard version uses 37,731 (3,719 of them in heapify) and the bottom-up version 22,655 — 40% fewer, and within 4% of . All four languages assert these exact counts, which doubles as a check that they execute the same algorithm.

def sift_down_counted(a: list[int], i: int, n: int, cnt: list[int]) -> None:
    while True:
        c = 2 * i + 1
        if c >= n:
            return
        if c + 1 < n:
            cnt[0] += 1
            if a[c] < a[c + 1]:
                c += 1
        cnt[0] += 1
        if a[i] >= a[c]:
            return
        a[i], a[c] = a[c], a[i]
        i = c


def sift_down_bottom_up(a: list[int], i: int, n: int, cnt: list[int]) -> None:
    """Floyd/Wegener: walk to a leaf along larger children (1 compare per level),
    climb back to where a[i] belongs, then rotate the path."""
    x, j = a[i], i
    while 2 * j + 2 < n:
        cnt[0] += 1
        j = 2 * j + 2 if a[2 * j + 1] < a[2 * j + 2] else 2 * j + 1
    if 2 * j + 1 < n:                   # a lone left child at the bottom
        j = 2 * j + 1
    while j > i:
        cnt[0] += 1
        if a[j] < x:
            j = (j - 1) // 2            # x belongs higher up
        else:
            break
    t, a[j] = a[j], x                   # x lands at j; path above shifts up one level
    while j > i:
        j = (j - 1) // 2
        a[j], t = t, a[j]


def heapsort_counted(a: list[int], bottom_up: bool) -> tuple[int, int]:
    """Sort in place; return (heapify comparisons, total comparisons)."""
    sift = sift_down_bottom_up if bottom_up else sift_down_counted
    cnt, n = [0], len(a)
    for i in range(n // 2 - 1, -1, -1):
        sift(a, i, n, cnt)
    build = cnt[0]
    for end in range(n - 1, 0, -1):
        a[0], a[end] = a[end], a[0]
        sift(a, 0, end, cnt)
    return build, cnt[0]


def minstd(seed: int, n: int, mod: int) -> list[int]:
    out, x = [], seed
    for _ in range(n):
        x = x * 48271 % 2147483647
        out.append(x % mod)
    return out


if __name__ == "__main__":
    a = [4, 10, 3, 5, 1, 8]
    assert heapsort_counted(a, False) == (7, 15) and a == [1, 3, 4, 5, 8, 10]
    a = [4, 10, 3, 5, 1, 8]
    assert heapsort_counted(a, True)[1] == 13 and a == [1, 3, 4, 5, 8, 10]
    r = minstd(42, 2000, 1_000_000)
    a = list(r)
    assert heapsort_counted(a, False) == (3719, 37731) and a == sorted(r)
    a = list(r)
    assert heapsort_counted(a, True)[1] == 22655 and a == sorted(r)
    for c in ([], [1], [2, 1], [5] * 50, list(range(100, 0, -1)), minstd(7, 500, 10)):
        b = list(c)
        heapsort_counted(b, True)
        assert b == sorted(c)
    print("ok")
import java.util.Arrays;

public class BottomUpHeapSort {
    static long cnt;

    static void siftDownCounted(int[] a, int i, int n) {
        while (true) {
            int c = 2 * i + 1;
            if (c >= n) return;
            if (c + 1 < n) { cnt++; if (a[c] < a[c + 1]) c++; }
            cnt++;
            if (a[i] >= a[c]) return;
            int t = a[i]; a[i] = a[c]; a[c] = t;
            i = c;
        }
    }

    static void siftDownBottomUp(int[] a, int i, int n) {
        int x = a[i], j = i;
        while (2 * j + 2 < n) {
            cnt++;
            j = a[2 * j + 1] < a[2 * j + 2] ? 2 * j + 2 : 2 * j + 1;
        }
        if (2 * j + 1 < n) j = 2 * j + 1;
        while (j > i) {
            cnt++;
            if (a[j] < x) j = (j - 1) / 2;
            else break;
        }
        int t = a[j];
        a[j] = x;
        while (j > i) {
            j = (j - 1) / 2;
            int u = a[j]; a[j] = t; t = u;
        }
    }

    /** Sorts in place; returns {heapify comparisons, total comparisons}. */
    static long[] heapsortCounted(int[] a, boolean bottomUp) {
        cnt = 0;
        int n = a.length;
        for (int i = n / 2 - 1; i >= 0; i--) {
            if (bottomUp) siftDownBottomUp(a, i, n); else siftDownCounted(a, i, n);
        }
        long build = cnt;
        for (int end = n - 1; end > 0; end--) {
            int t = a[0]; a[0] = a[end]; a[end] = t;
            if (bottomUp) siftDownBottomUp(a, 0, end); else siftDownCounted(a, 0, end);
        }
        return new long[] {build, cnt};
    }

    static int[] minstd(long seed, int n, int mod) {
        int[] out = new int[n];
        long x = seed;
        for (int k = 0; k < n; k++) { x = x * 48271 % 2147483647L; out[k] = (int) (x % mod); }
        return out;
    }

    static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }

    public static void main(String[] args) {
        int[] sortedSmall = {1, 3, 4, 5, 8, 10};
        int[] a = {4, 10, 3, 5, 1, 8};
        long[] r = heapsortCounted(a, false);
        check(r[0] == 7 && r[1] == 15 && Arrays.equals(a, sortedSmall), "standard small");
        a = new int[] {4, 10, 3, 5, 1, 8};
        check(heapsortCounted(a, true)[1] == 13 && Arrays.equals(a, sortedSmall), "bottom-up small");
        int[] base = minstd(42, 2000, 1_000_000), expect = base.clone();
        Arrays.sort(expect);
        a = base.clone();
        r = heapsortCounted(a, false);
        check(r[0] == 3719 && r[1] == 37731 && Arrays.equals(a, expect), "standard 2000");
        a = base.clone();
        check(heapsortCounted(a, true)[1] == 22655 && Arrays.equals(a, expect), "bottom-up 2000");
        System.out.println("ok");
    }
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>

static long long cnt = 0;

void siftDownCounted(std::vector<int>& a, int i, int n) {
    while (true) {
        int c = 2 * i + 1;
        if (c >= n) return;
        if (c + 1 < n) { ++cnt; if (a[c] < a[c + 1]) ++c; }
        ++cnt;
        if (a[i] >= a[c]) return;
        std::swap(a[i], a[c]);
        i = c;
    }
}

void siftDownBottomUp(std::vector<int>& a, int i, int n) {
    int x = a[i], j = i;
    while (2 * j + 2 < n) {
        ++cnt;
        j = a[2 * j + 1] < a[2 * j + 2] ? 2 * j + 2 : 2 * j + 1;
    }
    if (2 * j + 1 < n) j = 2 * j + 1;
    while (j > i) {
        ++cnt;
        if (a[j] < x) j = (j - 1) / 2;
        else break;
    }
    int t = a[j];
    a[j] = x;
    while (j > i) {
        j = (j - 1) / 2;
        std::swap(a[j], t);
    }
}

// Sorts in place; returns {heapify comparisons, total comparisons}.
std::pair<long long, long long> heapsortCounted(std::vector<int>& a, bool bottomUp) {
    cnt = 0;
    int n = static_cast<int>(a.size());
    for (int i = n / 2 - 1; i >= 0; --i) bottomUp ? siftDownBottomUp(a, i, n) : siftDownCounted(a, i, n);
    long long build = cnt;
    for (int end = n - 1; end > 0; --end) {
        std::swap(a[0], a[end]);
        bottomUp ? siftDownBottomUp(a, 0, end) : siftDownCounted(a, 0, end);
    }
    return {build, cnt};
}

std::vector<int> minstd(std::uint64_t seed, int n, int mod) {
    std::vector<int> out;
    std::uint64_t x = seed;
    for (int k = 0; k < n; ++k) { x = x * 48271 % 2147483647ULL; out.push_back(static_cast<int>(x % mod)); }
    return out;
}

int main() {
    const std::vector<int> sortedSmall{1, 3, 4, 5, 8, 10};
    std::vector<int> a{4, 10, 3, 5, 1, 8};
    assert((heapsortCounted(a, false) == std::pair<long long, long long>{7, 15}) && a == sortedSmall);
    a = {4, 10, 3, 5, 1, 8};
    assert(heapsortCounted(a, true).second == 13 && a == sortedSmall);
    auto base = minstd(42, 2000, 1000000), expect = base;
    std::sort(expect.begin(), expect.end());
    a = base;
    assert((heapsortCounted(a, false) == std::pair<long long, long long>{3719, 37731}) && a == expect);
    a = base;
    assert(heapsortCounted(a, true).second == 22655 && a == expect);
    std::cout << "ok\n";
}
let cnt = 0;

function siftDownCounted(a: number[], i: number, n: number): void {
  while (true) {
    let c = 2 * i + 1;
    if (c >= n) return;
    if (c + 1 < n) { cnt++; if (a[c] < a[c + 1]) c++; }
    cnt++;
    if (a[i] >= a[c]) return;
    const t = a[i]; a[i] = a[c]; a[c] = t;
    i = c;
  }
}

function siftDownBottomUp(a: number[], i: number, n: number): void {
  const x = a[i];
  let j = i;
  while (2 * j + 2 < n) {
    cnt++;
    j = a[2 * j + 1] < a[2 * j + 2] ? 2 * j + 2 : 2 * j + 1;
  }
  if (2 * j + 1 < n) j = 2 * j + 1;
  while (j > i) {
    cnt++;
    if (a[j] < x) j = Math.floor((j - 1) / 2);
    else break;
  }
  let t = a[j];
  a[j] = x;
  while (j > i) {
    j = Math.floor((j - 1) / 2);
    const u = a[j]; a[j] = t; t = u;
  }
}

/** Sorts in place; returns [heapify comparisons, total comparisons]. */
function heapsortCounted(a: number[], bottomUp: boolean): [number, number] {
  cnt = 0;
  const n = a.length;
  const sift = bottomUp ? siftDownBottomUp : siftDownCounted;
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) sift(a, i, n);
  const build = cnt;
  for (let end = n - 1; end > 0; end--) {
    const t = a[0]; a[0] = a[end]; a[end] = t;
    sift(a, 0, end);
  }
  return [build, cnt];
}

function minstd(seed: number, n: number, mod: number): number[] {
  const out: number[] = [];
  let x = seed;
  for (let k = 0; k < n; k++) { x = (x * 48271) % 2147483647; out.push(x % mod); }
  return out;
}

function check(ok: boolean, msg: string): void {
  if (!ok) throw new Error("check failed: " + msg);
}
const same = (x: number[], y: number[]) => x.length === y.length && x.every((v, k) => v === y[k]);

const sortedSmall = [1, 3, 4, 5, 8, 10];
let a = [4, 10, 3, 5, 1, 8];
check(same(heapsortCounted(a, false), [7, 15]) && same(a, sortedSmall), "standard small");
a = [4, 10, 3, 5, 1, 8];
check(heapsortCounted(a, true)[1] === 13 && same(a, sortedSmall), "bottom-up small");
const base = minstd(42, 2000, 1_000_000);
const expect = [...base].sort((x, y) => x - y);
a = [...base];
check(same(heapsortCounted(a, false), [3719, 37731]) && same(a, expect), "standard 2000");
a = [...base];
check(heapsortCounted(a, true)[1] === 22655 && same(a, expect), "bottom-up 2000");
console.log("ok");

Real-world uses

  • Introsort's safety net. C++ std::sort (libstdc++ and Microsoft's STL) runs quicksort and calls heap sort on any subarray whose recursion depth exceeds — see Quick Sort & Introsort. In libstdc++ that fallback is literally std::partial_sort(first, last, last), which is make_heap followed by sort_heap. Java's DualPivotQuicksort (current JDK) switches to its own heapSort when its depth counter passes MAX_RECURSION_DEPTH, and pdqsort (Go, Rust's older unstable sort) does the same after too many bad partitions. In all of these, heap sort is chosen because it is in place and worst-case — merge sort would need a buffer.
  • The Linux kernel. lib/sort.c describes itself as "a fast, small, non-recursive O(n log n) sort for the Linux kernel", and its sort_r() documentation says: "This function does a heapsort on the given array… Sorting time is O(n log n) both on average and worst-case. While quicksort is slightly faster on average, it suffers from exploitable O(n*n) worst-case behavior and extra memory requirements that make it less suitable for kernel use." The implementation is the bottom-up variant (its comment: "we find the sift-down path all the way to the leaves (one compare per level), then backtrack"), and claims comparisons on average. Kernel stacks are a few kilobytes and allocation in arbitrary contexts is not allowed, which is exactly the environment heap sort was made for. (Quotes checked against the current lib/sort.c in the mainline tree.)
  • Embedded and real-time systems. Hard real-time code needs a worst-case execution time bound and often forbids recursion and dynamic allocation (for example, under MISRA-style coding rules). Heap sort meets all three; quicksort meets none without extra engineering.
  • Partial sorting and top-k. std::partial_sort(first, middle, last) heapifies the first elements, sweeps the rest through the heap, then sort-heaps the prefix: . Python's heapq.nlargest / nsmallest use the same heap-select idea. Database engines implement ORDER BY … LIMIT k as a bounded heap ("top-N heapsort" in PostgreSQL's EXPLAIN ANALYZE output) instead of a full sort; see Query Planning & Optimization.
  • External sorting's merge phase. Merging sorted runs from disk uses a min-heap (or the closely related tournament / loser tree) of the run heads. Replacement selection, which generates runs about twice the memory size, is a heap-based variant of heap sort. Details in Sorting in the Real World.
  • Priority queues everywhere. The binary heap at the core of heap sort is the default priority queue in schedulers (CPU Scheduling), timer wheels' fallbacks, Dijkstra's algorithm (Graphs) and event-driven simulators. Heaps & Priority Queues covers those uses.

Pitfalls & edge cases

  • Sifting against the array length instead of the heap size. In the sort phase the heap is a[0..end-1]; passing n instead of end to sift-down pulls already-sorted elements back into the heap. Step 9 of the trace is the first place this would bite.
  • Off-by-one in the heapify start. The last internal node is n // 2 - 1 (0-indexed). Starting at n // 2 wastes one call on a leaf (harmless); starting at n // 2 - 2 skips a node (wrong result). With 1-indexed heaps the children are 2i and 2i+1 and the start is n // 2 — mixing the two conventions is a frequent source of bugs.
  • Comparing with only one child. Swapping with the left child when the right is larger breaks the heap property at the parent. Always pick the larger child (max-heap) or the smaller child (min-heap).
  • Min-heap by mistake. A min-heap with the "swap to the end" loop sorts descending. To sort ascending in place, use a max-heap.
  • Forgetting the lone child. When 2i + 1 == n - 1, node has a left child and no right child. c + 1 < n must be checked before reading a[c + 1].
  • Overflow in child index. For arrays near elements, 2 * i + 1 overflows a 32-bit int. Use 64-bit or size_t indices in C++ (as the C++ code above does).
  • Expecting adaptivity. Heap sort takes on already-sorted distinct input. If inputs are often nearly sorted, Timsort or insertion sort wins by orders of magnitude.
  • Expecting stability. See the three-element example above.
  • Using heapq for a max-heap in Python. Before Python 3.14, heapq offered only min-heap functions publicly, so the idiom is to push negated keys. Python 3.14 adds public heapify_max, heappush_max, heappop_max and friends (checked on 3.14.6); use them only if you can require 3.14.

Variations

Bottom-up heap sort (Floyd, Wegener). Described and implemented above: one comparison per level on the way down to a leaf, then a short climb. About comparisons on average, worst case. It does the same number of element moves as the standard version but fewer comparisons, which matters when comparisons are expensive (strings, records with a comparator callback — the Linux kernel case).

d-ary heap sort. Each node has children at d*i + 1 … d*i + d. The tree height drops to , so sift-down has fewer levels, but each level needs comparisons to find the largest child. or is often faster than in practice because the children of a node share a cache line and there are fewer levels of cache misses.

Weak-heap sort. Dutton's weak heaps (1993) relax the heap order to "every node is the nodes in its right subtree", which allows sorting with at most comparisons in the worst case (Edelkamp and Wegener, 2000) — about as close to as any practical in-place algorithm gets — at the cost of one extra bit per element.

Smoothsort. Dijkstra (1981) replaced the single binary heap with a forest of Leonardo-number-sized heaps so that already-sorted input sorts in while the worst case stays in place. It is adaptive where heap sort is not, but it is intricate and in practice slower than simpler adaptive sorts.

Heap select / partial sort. Keep a max-heap of the smallest elements seen so far; for each new element smaller than the root, replace the root and sift down. time, space, and it works on a stream. Sorting the heap at the end gives the smallest in order: that is std::partial_sort. When you do not need the order, quickselect is expected.

Tournament sort. Build a complete binary tree of "winners" bottom-up, output the root, replace the winner's leaf with and replay its path: comparisons but extra space. The loser-tree variant is used for -way merging in external sorts.

Priority-queue sorts with fancier heaps. Any priority queue gives a sort: a binomial, Fibonacci or pairing heap all yield , and a van Emde Boas tree or a radix heap on small integer keys can beat — but then you are no longer doing a comparison sort (Non-Comparison Sorts).

Practice ladder

Easy → hard. Most are heap problems rather than "implement heap sort", because the sift operations are what transfer. Descriptions are paraphrased; follow the links.

  1. Sort an Array (LeetCode 912) — sort without the built-in, . Teaches the full in-place heap sort and that it passes the adversarial tests that kill naive quicksort.
Hint

The canonical heapsort above, unchanged.

  1. Last Stone Weight (LeetCode 1046) — repeatedly smash the two heaviest stones. Teaches extract-max twice, insert once: a max-heap simulation.
Hint

Python: push negated weights into heapq. Each round pops two and pushes the difference if non-zero.

  1. Kth Largest Element in an Array (LeetCode 215) — find the k-th largest. Teaches partial heap sort: heapify then extractions (), or a size- min-heap ().
Hint

Heapify the whole array as a max-heap in , then do "swap root with end, shrink, sift" steps. The root is the answer.

Solution
def find_kth_largest(nums: list[int], k: int) -> int:
    a, n = list(nums), len(nums)

    def sift(i: int, size: int) -> None:
        while True:
            c = 2 * i + 1
            if c >= size:
                return
            if c + 1 < size and a[c] < a[c + 1]:
                c += 1
            if a[i] >= a[c]:
                return
            a[i], a[c] = a[c], a[i]
            i = c

    for i in range(n // 2 - 1, -1, -1):
        sift(i, n)
    for end in range(n - 1, n - k, -1):     # k-1 extractions
        a[0], a[end] = a[end], a[0]
        sift(0, end)
    return a[0]


assert find_kth_largest([3, 2, 1, 5, 6, 4], 2) == 5
assert find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) == 4
assert find_kth_largest([7], 1) == 7
print("ok")

time, extra space beyond the copy.

  1. Kth Largest Element in a Stream (LeetCode 703) — maintain the k-th largest as numbers arrive. Teaches the size- min-heap invariant: the root is the answer.
Hint

Keep a min-heap of the largest seen. On each add, push, and pop if the size exceeds .

  1. K Closest Points to Origin (LeetCode 973) — the k points nearest the origin. Teaches heap select with a max-heap of size keyed by squared distance.
Hint

Push (-dist, point); when size exceeds , pop. The heap holds the closest.

  1. Sort Characters By Frequency (LeetCode 451) — reorder a string by descending character frequency. Teaches heap-based ordering of aggregated keys (bucket sort also works).
Hint

Count with a dictionary, heapify (-count, char) pairs, pop in order.

  1. Merge k Sorted Lists (LeetCode 23) — merge sorted linked lists. Teaches the k-way merge with a min-heap of heads, the merge phase of external sorting.
Hint

Heap of (value, list_index, node); the index breaks ties so nodes are never compared.

Solution
import heapq


def merge_k_sorted(lists: list[list[int]]) -> list[int]:
    """Arrays stand in for linked lists; the heap logic is identical."""
    heap = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
    heapq.heapify(heap)
    out = []
    while heap:
        v, i, j = heapq.heappop(heap)
        out.append(v)
        if j + 1 < len(lists[i]):
            heapq.heappush(heap, (lists[i][j + 1], i, j + 1))
    return out


assert merge_k_sorted([[1, 4, 5], [1, 3, 4], [2, 6]]) == [1, 1, 2, 3, 4, 4, 5, 6]
assert merge_k_sorted([]) == [] and merge_k_sorted([[]]) == []
print("ok")

for total elements, heap space.

  1. Kth Smallest Element in a Sorted Matrix (LeetCode 378) — rows and columns sorted; find the k-th smallest. Teaches the k-way merge used as a selection procedure (binary search on value is the alternative).
Hint

Seed a min-heap with the first element of each row; pop times, pushing the next element of the popped row.

  1. Ugly Number II (LeetCode 264) — the n-th number whose only prime factors are 2, 3 and 5. Teaches generating a sorted sequence with a heap plus a seen-set (the three-pointer DP is faster).
Hint

Pop the smallest, push it times 2, 3 and 5 if not seen. The n-th pop is the answer.

  1. Qheap1 (HackerRank) — support insert, delete-arbitrary and get-min. Teaches heap deletion by index or by lazy deletion, which sorting never needs.
Hint
Lazy deletion: keep a second heap (or counter) of deleted values and discard tops that are marked deleted.
  1. Find Median from Data Stream (LeetCode 295) — running median. Teaches the two-heaps pattern: a max-heap of the lower half and a min-heap of the upper half.
Hint
Keep sizes balanced within one; the median is a root or the average of both roots.
  1. Single-Threaded CPU (LeetCode 1834) — simulate a CPU that always picks the shortest available task. Teaches sort-by-arrival plus a heap of available tasks keyed by (duration, index) — the core of shortest-job-first scheduling.
Hint
Sort tasks by enqueue time; advance time, pushing newly available tasks; if the heap is empty, jump time to the next arrival.
  1. Smallest Range Covering Elements from K Lists (LeetCode 632) — the smallest interval containing at least one element from each of sorted lists. Teaches k-way merge with a running maximum. Hard.
Hint
Min-heap of one element per list plus the current maximum. The range is `[heap min, current max]`; advance the list that owned the minimum and update. Stop when any list is exhausted.
Solution
```python
import heapq


def smallest_range(nums: list[list[int]]) -> list[int]:
    heap = [(lst[0], i, 0) for i, lst in enumerate(nums)]
    heapq.heapify(heap)
    cur_max = max(lst[0] for lst in nums)
    best = [heap[0][0], cur_max]
    while True:
        v, i, j = heapq.heappop(heap)
        if cur_max - v < best[1] - best[0]:
            best = [v, cur_max]
        if j + 1 == len(nums[i]):
            return best
        nxt = nums[i][j + 1]
        cur_max = max(cur_max, nxt)
        heapq.heappush(heap, (nxt, i, j + 1))


assert smallest_range([[4, 10, 15, 24, 26], [0, 9, 12, 20], [5, 18, 22, 30]]) == [20, 24]
assert smallest_range([[1, 2, 3], [1, 2, 3], [1, 2, 3]]) == [1, 1]
print("ok")
```

<span class="math" data-tex="O(N \log k)"></span> for <span class="math" data-tex="N"></span> total elements.

Common mistakes & interview follow-ups

"Why is building a heap O(n) when it does n/2 sift-downs of O(log n) each?" Because most sift-downs are short: half the nodes are leaves (zero work), a quarter walk one level, an eighth two levels. The total is swaps. The bound is correct but not tight. Being able to derive on the whiteboard is the expected answer.

"Heap sort and merge sort are both O(n log n) worst case. When do you pick heap sort?" When extra memory is not available (merge sort needs ) or recursion is forbidden. Pick merge sort when you need stability, are sorting linked lists, or are sorting externally.

"Why is heap sort slower than quicksort in practice?" Cache misses: sift-down jumps from to , so each level beyond the cache is a miss, while quicksort scans sequentially. Also about 2× the comparisons of a median-of-3 quicksort for the standard version, and unpredictable branches.

"Can heap sort be made stable?" Only by attaching the original index to each key as a tie-breaker, which costs extra space — at which point merge sort is simpler.

"Is heap sort adaptive?" No. Sorted input still costs ; reverse-sorted input is already a max-heap so heapify is cheap, but the sort phase is not. Smoothsort is the adaptive heap-based sort.

"What if you only need the top k?" Don't sort: heap select with a size- heap, and streamable, or quickselect, expected.

"Implement heapify without recursion." The iterative while loop in this page's code is the answer; mention that it is why heap sort needs stack.

"What does introsort use heap sort for, and why not merge sort?" As the fallback when quicksort's depth exceeds . Heap sort keeps the whole algorithm in place; merge sort would need a buffer.

Quick quiz

1. In a 0-indexed max-heap stored in an array of size 10, which indices are leaves, and where does heapify start?

Answer

Leaves are indices 5..9 (n // 2 to n - 1). Heapify starts at index 4 (n // 2 - 1), whose only child is index 9.

2. Heapify does at most how many swaps on an array of 12 elements? Use the exact formula.

Answer

At most where counts 1 bits. has two 1 bits, so at most swaps (the sum of node heights in a 12-node heap).

3. Why does the element swapped to the root during the sort phase usually sink nearly to the bottom, and which variant exploits that?

Answer

It came from the last position of the heap, a leaf, so it is typically among the smallest remaining elements and belongs near the bottom. Bottom-up heap sort descends to a leaf first with one comparison per level and then climbs back a short distance, roughly halving comparisons.

4. Give the smallest input showing heap sort is unstable.

Answer

Two equal keys: [(1, a), (1, b)]. The heap is already valid; the first extraction swaps root and last, giving [(1, b), (1, a)].

5. At integers, heap sort ran about 2–3× slower than std::sort in our measurement, but at it was faster. What changed?

Answer

The array stopped fitting in cache. At 400 KB it fits in L2/L3 and heap sort's jumps are cheap; at 40 MB every deep level of each sift-down is a cache miss, while quicksort's sequential scans keep streaming from memory efficiently.

Further reading / sources

  • J. W. J. Williams, "Algorithm 232: Heapsort", Communications of the ACM 7(6), 1964 — the heap and heap sort.
  • Robert W. Floyd, "Algorithm 245: Treesort 3", Communications of the ACM 7(12), 1964 — linear-time bottom-up heap construction.
  • Ingo Wegener, "BOTTOM-UP-HEAPSORT, a new variant of HEAPSORT beating, on an average, QUICKSORT (if n is not very small)", Theoretical Computer Science 118(1), 1993.
  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 4th ed. — Chapter 6 (heaps, BUILD-MAX-HEAP in with the summation proof, heapsort).
  • Robert Sedgewick and Kevin Wayne, Algorithms, 4th ed. — §2.4 (priority queues, heapsort, and the observation that heapsort is rarely used because of poor cache performance).
  • Donald E. Knuth, The Art of Computer Programming, Vol. 3, §5.2.3 — heapsort analysis and Floyd's improvement.
  • Anthony LaMarca and Richard E. Ladner, "The Influence of Caches on the Performance of Heaps" (ACM JEA, 1996) and "The Influence of Caches on the Performance of Sorting" (SODA 1997).
  • Edsger W. Dijkstra, "Smoothsort, an alternative for sorting in situ", Science of Computer Programming 1(3), 1982 (EWD796a, 1981).
  • Linux kernel source, lib/sort.c — the production bottom-up heapsort quoted above.

Lessons: previous — Quick Sort, Partition Schemes & Introsort · next — Non-Comparison Sorts & the Lower Bound · module — Searching & Sorting · course map.

Related Archon pages: Heaps & Priority Queues · Sorting & Searching (overview) · Elementary Sorts · Sorting in the Real World · Quickselect & Order Statistics · Data Structures in Memory · CPU Scheduling.