Using sink to Build a Heap

One approach is to work from the top: sink the root, then sink the nodes on the next level, and so on down. Let’s just try sinking the root and see what we get.

5 is larger than its smaller child 3, so they swap:

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

Now 5 is larger than its smaller child, 1, so they swap again; 5 is now at a leaf:

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

The new root 3 is still larger than its child 1, so we sink the new root as well:

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

Next we sink the nodes on the second level, 3 and 8. 3 is already smaller than its children, so it is done. 8 is larger than its only child, 2, so they swap:

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

The order property now holds, but only because the value that moved up into the right child, 2, is not smaller than the root. If it were, we would have to sink the root again. In general, a sink on one level can move a small value up and break the order property on the level above, so we would have to go back up and check nodes again, with no clear rule for when to stop. That is not a good way to build a heap.

Sinking from the bottom up

Look back at why sink works in remove. There we put a value at the root of a tree whose two subtrees are already heaps, and that is what lets a single sink push the value down until it is no larger than either child.

Here the root’s subtrees are not heaps, so sinking the root only moves one value down through subtrees that are out of order.

So how about we make a node’s two subtrees into heaps before sinking the node itself? That means working from the bottom up. Each leaf is already a heap of size one. So a parent of leaves has two subtrees that are heaps, and one sink fixes it. That parent is now the root of a heap, so the nodes on the level above it also have subtrees that are heaps, and one sink fixes each of them. This continues level by level up to the root. Each internal node is sunk once, and no node has to be revisited.