Problem: Building the Heap Top-Down

The chapter built the heap from the bottom up, sinking each internal node, and that build was $O (n)$ . There is another way to turn an array into a heap: insert the elements one at a time, letting each new element swim up to where it belongs. That is the same as calling the heap’s add once for each element.

The elements are already in the array, so inserting them one at a time means iterating over the array from front to back. At index i, treat the slots before i as a heap that is already built, and swim the element at i up into it. When the iteration reaches the end, the whole array is a heap.

Build a max-heap, the kind heapsort uses. In a max-heap a node is no smaller than its children, so a node is out of place when it is larger than its parent, and swim moves it up while that is the case.

Here is the array to build from:

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

The same array laid out as a complete binary tree:

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

Exercise

Write buildHeapTopDown(int[] arr), which rearranges arr into a max-heap by swimming each element up in turn. You will need a swim helper that works on the bare array, the way the chapter adapted sink to take the array as a parameter. Swim needs the parent index, so add this helper, along with a swap helper like the chapter’s:

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

Before opening the solution, answer two questions:

What is the total cost of this build?
The bottom-up build was $O (n)$ . Is this one the same? Both visit every node, and both swim and sink cost $O (lo g n)$ per call. If the totals differ, where does the difference come from?