Building a Heap from an Array

We have an array of values, and we want to rearrange it into a heap in place. The approach is to look at the array we are handed as though it were already a heap’s array, then ask what is right about it and what is wrong.

Take the running example, [5, 3, 8, 1, 9, 2], and read it in level order, the way the binary heap chapter stored a tree: index 0 is the root, the next two are its children, and so on.

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

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

Because the array has no gaps, the tree that comes out is complete: every level is full except possibly the last, and the last fills from the left. That is the structure property, so the array already has the heap’s shape, whatever the values are.

The order property does not hold. The root 5 sits above 3, the node 8 sits above 2, and small values sit below larger ones in several places in the tree. So to turn this array into a heap, we only have to fix the order property. The shape can stay as it is.

Operations we already have

The binary heap chapter gave us two operations that fix the order property at a single node: swim moves a node up past its parent, and sink moves a node down past its smaller child, until the order property holds there.

Take sink. It is used in remove to push a value down from the root until it is no larger than either child. How about we try to use it here?