Algorithms standard

Build a max-heap from an unsorted array

Take an unsorted array of 7 numbers and transform it into a max-heap in O(n), running sift-down at each internal node from the deepest backward to the root.

concept: Heap Sort

#heap #sift-down #heap-sort #array #in-place

Problem

Take the array

a = [3, 1, 6, 5, 2, 4, 8]    # n = 7

and rearrange it in place into a max-heap. Show every step. Count the swaps.

Approach

The array is a tree. Index $i$ 's children are at $2 i + 1$ and $2 i + 2$ . Drawn out:

        3        <- a[0]
      /   \
     1     6     <- a[1], a[2]
    / \   / \
   5   2 4   8  <- a[3], a[4], a[5], a[6]

We call sift_down at every internal node, starting from the deepest internal node and walking back to the root. With $n = 7$ , the deepest internal node is at index $⌊ n /2 ⌋ - 1 = 2$ . So we run sift-down at indices 2, 1, 0 in that order.

Why bottom-up? Sift-down needs both child subtrees to already be heaps. Going from the bottom up guarantees that — by the time we sift-down at index $i$ , both children's subtrees have already been processed.

Walkthrough

Step 1 — sift_down(a, 2, 7)

Index 2 holds 6. Children are a[5] = 4 and a[6] = 8.

Largest child: a[6] = 8. Is 8 > 6? Yes. Swap.

a = [3, 1, 8, 5, 2, 4, 6]

Now sit at index 6. It's a leaf — no children inside the array. Sift-down terminates.

        3
      /   \
     1     8
    / \   / \
   5   2 4   6

Swaps so far: 1.

Step 2 — sift_down(a, 1, 7)

Index 1 holds 1. Children are a[3] = 5 and a[4] = 2.

Largest child: a[3] = 5. Is 5 > 1? Yes. Swap.

a = [3, 5, 8, 1, 2, 4, 6]

Now sit at index 3. Leaf. Done.

        3
      /   \
     5     8
    / \   / \
   1   2 4   6

Swaps so far: 2.

Step 3 — sift_down(a, 0, 7)

Index 0 holds 3. Children are a[1] = 5 and a[2] = 8.

Largest child: a[2] = 8. Is 8 > 3? Yes. Swap.

a = [8, 5, 3, 1, 2, 4, 6]

Now sit at index 2 (where the 3 now lives). Children are a[5] = 4 and a[6] = 6. Largest: 6. Is 6 > 3? Yes. Swap.

a = [8, 5, 6, 1, 2, 4, 3]

Now sit at index 6. Leaf. Done.

Swaps so far: 4.

Final state

a = [8, 5, 6, 1, 2, 4, 3]

        8
      /   \
     5     6
    / \   / \
   1   2 4   3

Check the heap property at every parent–child pair: 8 ≥ 5, 8 ≥ 6, 5 ≥ 1, 5 ≥ 2, 6 ≥ 4, 6 ≥ 3. All good. $a [0] = 8$ is the max of the array.

Answer

a = [8, 5, 6, 1, 2, 4, 3]. 4 swaps total across 3 sift-down calls. Two of the calls did one swap each (cheap leaf-adjacent sifts), and the third call sifted two levels down.

Remarks

The "swap count" pattern here is exactly what makes build-heap surprisingly cheap. Half the internal nodes sit one level above the leaves and do at most 1 swap. A quarter sit two levels up and do at most 2. The total sum is geometric — it stays linear in $n$ , not $n lo g n$ like you might guess.

From here, heap sort proceeds by repeatedly swapping a[0] with the last element of the heap, shrinking the heap by one, and calling sift-down at the root. The max value lands in its sorted slot each round.