The Heap Properties

The questions in this section are about the min-heap, the binary heap that serves the smallest element first.

Solution

The structure property: the tree is complete, meaning every level is full except possibly the last, and the nodes on the last level are as far left as they can be. The order property: no node holds a value larger than its children.

Exercise

For each tree below, decide whether it is a min-heap. If it is not, name the property it breaks and where.

Tree A:

               ╭───╮
               │ 3 │
               ╰─┬─╯
       ┌─────────┴─────────┐
     ╭─┴─╮               ╭─┴─╮
     │ 6 │               │ 4 │
     ╰─┬─╯               ╰─┬─╯
  ┌────┴────┐          ┌───┘
╭─┴─╮     ╭─┴─╮      ╭─┴─╮
│ 8 │     │ 9 │      │ 5 │
╰───╯     ╰───╯      ╰───╯

Tree B:

             ╭───╮
             │ 2 │
             ╰─┬─╯
       ┌───────┴───────┐
     ╭─┴─╮           ╭─┴─╮
     │ 7 │           │ 5 │
     ╰─┬─╯           ╰───╯
  ┌────┴────┐
╭─┴─╮     ╭─┴─╮
│ 9 │     │ 4 │
╰───╯     ╰───╯

Tree C:

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

Solution

Tree A is a min-heap. It is complete, and every node is no larger than its children: 3 is smaller than 6 and 4, 6 is smaller than 8 and 9, and 4 is smaller than 5.

Tree B is not a min-heap. It is complete, but it breaks the order property at 7, whose child 4 is smaller than it.

Tree C is not a min-heap. Every node is no larger than its children, but the tree is not complete: the last level has a node under 6 while the positions under 3, which must fill first, are empty.

Solution

A perfect binary tree exists only when the number of nodes is $2^{h + 1} - 1$ for some height $h$ , but a heap must hold any number of elements. A complete binary tree exists for every number of nodes.