Heapsort

Sort an array using a binary heap — O(N log N) and in-place.

Intuition

Heapsort solves the sorting problem in two phases:

1. Build a max-heap out of the array (so largest is at index 1).
2. Repeatedly swap the root with the last unsorted element, shrink the heap by 1, and re-heapify.

The heap property

A max-heap is an array we interpret as a binary tree where every parent ≥ its children. The array layout (using 1-indexing):

• Parent of index i → i / 2 (integer division)
• Left child → 2i
• Right child → 2i + 1

Example: the array [100, 19, 36, 17, 3, 25, 1, 2, 7] is a valid max-heap. Visually:

Notice: 100 ≥ 19 and 36; 19 ≥ 17 and 3; 36 ≥ 25 and 1; 17 ≥ 2 and 7. ✓

Key consequence: the max value of the heap is always at index 1 — getting the max is O(1).

The algorithm

HEAPSORT(table[1..N]):
    BuildHeap(table, N)              // turn array into a max-heap
    for i = N down to 2:
        swap table[1] and table[i]   // largest element to end
        BuildHeap(table, i-1)        // re-heapify on the shrunk range

BuildHeap(table, size):
    // ensure every parent is ≥ its children
    for index = size down to 1:
        leftChild  = 2 * index
        rightChild = 2 * index + 1
        biggest    = index
        if leftChild  <= size and table[leftChild]  > table[biggest]: biggest = leftChild
        if rightChild <= size and table[rightChild] > table[biggest]: biggest = rightChild
        if biggest != index:
            swap table[index] and table[biggest]
            // (and continue sifting down — done iteratively in practice)

Interactive demo

Step-by-step walkthrough

Starting array: 25, 17, 36, 2, 3, 100, 1, 19, 7

Phase 1 — Build the max-heap

Walk from the last index back to 1 and sift each node down. After BuildHeap:

[100, 19, 36, 17, 3, 25, 1, 2, 7]    ✓ heap property holds

Phase 2 — Repeatedly swap and shrink

Step  Array (sorted suffix in italics)
1     swap 100 ↔ 7  → [7, 19, 36, 17, 3, 25, 1, 2, 100]
1.5   re-heapify    → [36, 19, 25, 17, 3, 7, 1, 2, 100]
2     swap 36 ↔ 2   → [2, 19, 25, 17, 3, 7, 1, 36, 100]
2.5   re-heapify    → [25, 19, 7, 17, 3, 2, 1, 36, 100]
3     swap 25 ↔ 1   → [1, 19, 7, 17, 3, 2, 25, 36, 100]
3.5   re-heapify    → [19, 17, 7, 1, 3, 2, 25, 36, 100]
…     continue until everything is sorted
final               → [1, 2, 3, 7, 17, 19, 25, 36, 100]

Complexity

• Space: O(1) extra — sorting is in-place.
• Stable? No — equal elements can be reordered.

Exam tips