The Structure Property

The structure property requires a heap to be a complete binary tree. A binary tree is complete when every level is full, except possibly the last, and the nodes on the last level are as far to the left as they can be. You fill the tree one level at a time from the top, and within each level you add nodes from left to right.

Here is a complete binary tree with six nodes:

               ╭───╮
               │ ● │
               ╰─┬─╯
       ┌─────────┴─────────┐
     ╭─┴─╮               ╭─┴─╮
     │ ● │               │ ● │
     ╰─┬─╯               ╰─┬─╯
  ┌────┴────┐          ┌───┘
╭─┴─╮     ╭─┴─╮      ╭─┴─╮
│ ● │     │ ● │      │ ● │
╰───╯     ╰───╯      ╰───╯

The top two levels are full. The last level holds three nodes, and they fill the three leftmost positions: both children of the left node, then the left child of the right node.

Complete is not the same as perfect

In the search tree chapter we defined the perfect binary tree, where every level is full, including the last:

                ╭───╮
                │ ● │
                ╰─┬─╯
       ┌──────────┴──────────┐
     ╭─┴─╮                 ╭─┴─╮
     │ ● │                 │ ● │
     ╰─┬─╯                 ╰─┬─╯
  ┌────┴────┐           ┌────┴────┐
╭─┴─╮     ╭─┴─╮       ╭─┴─╮     ╭─┴─╮
│ ● │     │ ● │       │ ● │     │ ● │
╰───╯     ╰───╯       ╰───╯     ╰───╯

A perfect binary tree of height $h$ has exactly $2^{h + 1} - 1$ nodes: 1, 3, 7, 15, and so on. Every perfect tree is also complete, because “every level full” is a special case of “every level full except possibly the last.” A complete tree does not have to be perfect, as the six-node tree above shows.

This difference is why a heap needs a complete tree and not a perfect one. A heap has to hold any number of elements, and a perfect tree exists only when the number of nodes is $2^{h + 1} - 1$ for some height $h$ . For any number of nodes, there is exactly one complete shape that holds them. Because the number of nodes fixes the shape, we can later store a heap in a plain array, with no left and right references at all.

When a tree is not complete

A tree fails to be complete in one of two ways: a level above the last is not full, or the last level has a gap with a node to the right of it. Here is a tree that fails:

        ╭───╮
        │ ● │
        ╰─┬─╯
  ┌───────┴───────┐
╭─┴─╮           ╭─┴─╮
│ ● │           │ ● │
╰───╯           ╰─┬─╯
             ┌────┴────┐
           ╭─┴─╮     ╭─┴─╮
           │ ● │     │ ● │
           ╰───╯     ╰───╯

The bottom level has nodes under the right child but none under the left child, and the positions under the left child must fill first. So the tree is not complete.