RavnaryA Knowledge Platform
Colour theme

Card 01/ 07

Take the quiz

ConceptDifficulty: Intermediate4 min

Heapsort: Build a Max-Heap, Then Move the Largest to the End

The array holds a heap at the front and the sorted items at the back, and the boundary moves one step per extraction.

Heapsort is a sorting algorithm that turns the array into a max-heap, a heap in which every parent is at least as large as its children, and then repeatedly swaps the root, the largest item left, to the back of the heap. This card covers the two phases, the boundary between the heap and the sorted items, why no second array is needed, and the signs that heapsort is the sort to reach for.

The first phase builds the max-heap inside the array, which takes O(n) time. The second phase extracts. The root is the largest item in the heap, and its final place in the sorted array is the last slot the heap occupies, so heapsort swaps the root with the heap's last item, shrinks the heap by one, and sifts the new root down to restore the heap. The slot the heap gave up now holds the item that belongs there. After every extraction the array is in two parts: a max-heap at the front, from index 0 to a boundary end, and the sorted items after it, each already in its final place. Each extraction moves end one step left, and when the heap holds one item the array is sorted.

Starting from the max-heap 9 7 8 4 5 2, which a bottom-up build makes from 4 7 2 9 5 8, the extraction phase runs five times. The trace has one frame per extraction, and end marks the last index still inside the heap.

Heapsort's extraction phase on the max-heap 9 7 8 4 5 2

Input9 7 8 4 5 2

  1. Max-heap

    1. 9
    2. 7
    3. 8
    4. 4
    5. 5
    6. 2end

    The max-heap built from 4 7 2 9 5 8 fills the array, so the heap ends at index 5 and the sorted part is empty.

  2. 9 to index 5

    1. 8
    2. 7
    3. 2
    4. 4
    5. 5end
    6. 9

    The root, 9, swaps with 2, the last item of the heap, and stays at index 5 for good. 2 sifts down past 8, and the heap now ends at index 4.

  3. 8 to index 4

    1. 7
    2. 5
    3. 2
    4. 4end
    5. 8
    6. 9

    8 swaps with 5 and stays at index 4. 5 sifts down past 7, and the heap is indices 0 to 3.

  4. 7 to index 3

    1. 5
    2. 4
    3. 2end
    4. 7
    5. 8
    6. 9

    7 swaps with 4 and stays at index 3. 4 sifts down past 5.

  5. 5 to index 2

    1. 4
    2. 2end
    3. 5
    4. 7
    5. 8
    6. 9

    5 swaps with 2 and stays at index 2. 2 sifts down past 4.

  6. 4 to index 1

    1. 2end
    2. 4
    3. 5
    4. 7
    5. 8
    6. 9

    4 swaps with 2 and stays at index 1. The one item left in the heap is the smallest, so the array is sorted.

Result2 4 5 7 8 9

Five extractions sorted six items, and each one placed the largest item left in the heap, 9, then 8, 7, 5 and 4. That is why heapsort uses a max-heap: the largest item belongs at the back, which is exactly the slot the shrinking heap frees. A min-heap would hand over the smallest item, whose place is at the front, where the heap still lives.

A play-off for places on a podium works the same way. The winner of a play-off takes the last free place, counting from the bottom, and the play-off is rerun among those left. The analogy breaks on the losers. A play-off eliminates them, while every item in a heap is eventually crowned, each in its turn.

Pushing every item into a separate heap and popping them into a new list also sorts, and in Python it is a few lines with heapq. It is not heapsort: it holds two collections of n items at once, where heapsort keeps the heap and the sorted part in the one array, with O(1) extra memory.

Heapsort on an array of n items
Best case
O(n log n)
on inputs with distinct items; each sift-down can travel the height of the heap
Average case
O(n log n)
any input order
Worst case
O(n log n)
on every input; no order of the items is slow
Extra space
O(1)
the heap and the sorted part share the array
Stable
No
the swap to the end can jump over an equal item
In place
Yes
no second array and no recursion

Two signs point to heapsort, and they have to appear together. You need O(n log n) on every input, with no slow case for an unlucky or hostile input to find, which rules out a plain quicksort. And you cannot spare more memory than the array itself, which rules out merge sort and its O(n) buffer. Stability must not matter either, since heapsort does not keep equal items in their input order. Where any of the three conditions is relaxed, another sort is usually faster in practice, and Choosing a Sorting Algorithm, a later topic, weighs them.

← → move through sections and cards