Tracing the Build

To build a heap, we read the array as a complete tree. Then we fix the order property by sinking each internal node, working from the bottom up.

Here are the starting array and the tree it describes:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 5 │ 3 │ 8 │ 1 │ 9 │ 2 │
└───┴───┴───┴───┴───┴───┘

               ╭───╮
               │ 5 │
               ╰─┬─╯
       ┌─────────┴─────────┐
     ╭─┴─╮               ╭─┴─╮
     │ 3 │               │ 8 │
     ╰─┬─╯               ╰─┬─╯
  ┌────┴────┐          ┌───┘
╭─┴─╮     ╭─┴─╮      ╭─┴─╮
│ 1 │     │ 9 │      │ 2 │
╰───╯     ╰───╯      ╰───╯

The leaves 1, 9, and 2 have no children, so each is already a one-node heap, and we leave them alone. The internal nodes are 5, 3, and 8. We sink them from the bottom up, which in the array means starting at the last internal node and working back toward the root: index 2, then index 1, then index 0.

Index 2: sink 8

8 has a single child, 2. Since $8>2$, they swap, and 8 lands at a leaf:

               ╭───╮
               │ 5 │
               ╰─┬─╯
       ┌─────────┴─────────┐
     ╭─┴─╮               ╭─┴─╮
     │ 3 │               │░2░│
     ╰─┬─╯               ╰─┬─╯
  ┌────┴────┐          ┌───┘
╭─┴─╮     ╭─┴─╮      ╭─┴─╮
│ 1 │     │ 9 │      │░8░│
╰───╯     ╰───╯      ╰───╯

The subtree rooted at index 2 is now a heap. In the array: [5, 3, 2, 1, 9, 8].

Index 1: sink 3

3 has children 1 and 9. The smaller is 1, and $3>1$, so they swap; 3 lands at a leaf:

               ╭───╮
               │ 5 │
               ╰─┬─╯
       ┌─────────┴─────────┐
     ╭─┴─╮               ╭─┴─╮
     │░1░│               │ 2 │
     ╰─┬─╯               ╰─┬─╯
  ┌────┴────┐          ┌───┘
╭─┴─╮     ╭─┴─╮      ╭─┴─╮
│░3░│     │ 9 │      │ 8 │
╰───╯     ╰───╯      ╰───╯

The subtree rooted at index 1 is now a heap. In the array: [5, 1, 2, 3, 9, 8].

Index 0: sink 5

Both of the root’s subtrees are already heaps. That is exactly the condition sink needs, so this one sink finishes the whole tree.

5 has children 1 and 2. The smaller is 1, and $5>1$, so they swap:

               ╭───╮
               │░1░│
               ╰─┬─╯
       ┌─────────┴─────────┐
     ╭─┴─╮               ╭─┴─╮
     │░5░│               │ 2 │
     ╰─┬─╯               ╰─┬─╯
  ┌────┴────┐          ┌───┘
╭─┴─╮     ╭─┴─╮      ╭─┴─╮
│ 3 │     │ 9 │      │ 8 │
╰───╯     ╰───╯      ╰───╯

5 is not settled yet: it now has children 3 and 9. The smaller is 3, and $5>3$, so they swap again, and 5 lands at a leaf:

               ╭───╮
               │ 1 │
               ╰─┬─╯
       ┌─────────┴─────────┐
     ╭─┴─╮               ╭─┴─╮
     │░3░│               │ 2 │
     ╰─┬─╯               ╰─┬─╯
  ┌────┴────┐          ┌───┘
╭─┴─╮     ╭─┴─╮      ╭─┴─╮
│░5░│     │ 9 │      │ 8 │
╰───╯     ╰───╯      ╰───╯

The heap is built

Every internal node has been sunk once, and each node is now no larger than its children:

  0   1   2   3   4   5
┌───┬───┬───┬───┬───┬───┐
│ 1 │ 3 │ 2 │ 5 │ 9 │ 8 │
└───┴───┴───┴───┴───┴───┘

The array is now a heap. We rearranged it in place.