Solution: Swimming Each Element Up

The build

Iterate over the array from front to back, swimming each element up into the heap formed by the slots before it:

public static void buildHeapTopDown(int[] arr) {
  for (int i = 1; i < arr.length; i++) {
    swim(arr, i);
  }
}

The loop starts at i = 1, not 0. A single element, arr[0] on its own, is already a heap, so there is nothing to swim there.

swim is the operation from the binary heap chapter, adapted to take the array as a parameter and to build a max-heap, so a node swims up while it is larger than its parent:

private static void swim(int[] arr, int i) {
  while (i > 0 && arr[i] > arr[parent(i)]) {
    swap(arr, i, parent(i));
    i = parent(i);
  }
}

// The parent of the node at index i. Pre: i > 0.
private static int parent(int i) {
  return (i - 1) / 2;
}

swim needs no size bound the way sink does. It only ever moves toward index 0, so it never goes past the end of the array.

Tracing the build

Iterate i from 1 to 5 on the array [5, 3, 8, 1, 9, 2]:

i = 1: 3 against its parent 5. 3 > 5 is false, so 3 stays.

    ╭───╮
    │ 5 │
    ╰─┬─╯
  ┌───┘
╭─┴─╮
│█3█│
╰───╯

i = 2: 8 against its parent 5. 8 > 5, so they swap. 8 is now at the root and stops. The array is [8, 3, 5, 1, 9, 2].

     ╭───╮
     │░8░│
     ╰─┬─╯
  ┌────┴────┐
╭─┴─╮     ╭─┴─╮
│ 3 │     │░5░│
╰───╯     ╰───╯

i = 3: 1 against its parent 3. 1 > 3 is false, so 1 stays.

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

i = 4: 9 against its parent 3. 9 > 3, so they swap, and 9 moves to index 1.

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

Now 9 is against its parent 8. 9 > 8, so they swap again, and 9 reaches the root. The array is [9, 8, 5, 1, 3, 2].

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

i = 5: 2 against its parent 5. 2 > 5 is false, so 2 stays.

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

The result is a max-heap:

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

The chapter’s bottom-up build produced [9, 5, 8, 1, 3, 2] from the same array. Both are valid max-heaps. A build only has to put the elements in heap order, and more than one arrangement of the same elements is in heap order.

What it costs

swim moves a node up, one level per step, and stops at the root at the latest. So the most a node can swim is its depth, the number of levels above it. This is the reverse of the bottom-up build, where the most a node can sink is its height, the number of levels below it.

Count the work level by level, this time from the top down. For each level, write down the most a node on that level can cost:

The root, depth $0$ : $0$ steps, and there is one root.
One level down, depth $1$ : at most $1$ step, and there are two nodes.
Two levels down, depth $2$ : at most $2$ steps, and there are four nodes.
… and so on. Each level down has twice as many nodes, and the step bound goes up by one …
The deepest levels, depth about $lo g n$ : at most $lo g n$ steps, and they contain a linear number of nodes.

In a heap, the leaves are exactly the back half of the array, and they sit on the deepest levels. In the worst case, many of those nodes can swim on the order of $lo g n$ steps, so the leaves alone can take on the order of $n lo g n$ work. No single swim costs more than $O (lo g n)$ , so the top-down build has worst-case cost

top-down build cost = O (n lo g n) .

Why the bottom-up build is cheaper

The leaves have height $0$ , so sinking them takes no steps, but they have depth about $lo g n$ , so swimming them can be the most expensive work in the tree. When you sink from the bottom up, the expensive nodes are at the top, and there are few of them, so the total comes to $O (n)$ . When you swim from the top down, the expensive nodes are at the bottom, and there are many of them, so the total comes to $O (n lo g n)$ . The chapter’s first heapsort added the elements to a heap one at a time. That is this same top-down build, so that build was $O (n lo g n)$ . Moving to the bottom-up build lowered it to $O (n)$ .