add: Insert and Swim Up

add has to put a new element into the heap and leave both properties holding. We do that in two steps: first place the element so the tree stays complete, then move it up until the order property holds again.

Start with the structure property. A heap is a complete binary tree, so there is only one place a new node can go: the next open slot on the bottom level, just to the right of the last node. (If the bottom level is already full, the slot is the first position of a new level.)

Consider this heap:

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

Let’s add 1 to this heap. The only open slot is under 4 on the right:

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

The tree is still complete, so the structure property holds. The order property can break, though, and here it does. The new node, 1, is smaller than its parent, 4, so the child outranks the parent. We fix this by letting the new node swim up.

Compare the new node with its parent.

                ╭───╮
                │ 2 │
                ╰─┬─╯
       ┌──────────┴──────────┐
     ╭─┴─╮                 ╭─┴─╮
     │ 5 │                 │░4░│
     ╰─┬─╯                 ╰─┬─╯
  ┌────┴────┐           ┌────┴────┐
╭─┴─╮     ╭─┴─╮       ╭─┴─╮     ╭─┴─╮
│ 9 │     │ 7 │       │ 6 │     │█1█│
╰───╯     ╰───╯       ╰───╯     ╰───╯

If the new node outranks the parent, swap the two. Here 1 is smaller than 4, so they swap:

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

Now compare 1 with its new parent, 2.

                ╭───╮
                │░2░│
                ╰─┬─╯
       ┌──────────┴──────────┐
     ╭─┴─╮                 ╭─┴─╮
     │ 5 │                 │█1█│
     ╰─┬─╯                 ╰─┬─╯
  ┌────┴────┐           ┌────┴────┐
╭─┴─╮     ╭─┴─╮       ╭─┴─╮     ╭─┴─╮
│ 9 │     │ 7 │       │ 6 │     │ 4 │
╰───╯     ╰───╯       ╰───╯     ╰───╯

Again 1 is smaller, so they swap:

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

The new node is now the root, so there is no parent left to compare with, and add stops.

The new node does not always move. Go back to the heap we started with and add a value larger than 4, say 5. The new node goes in the only open slot, under 4:

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

Since 5 is larger than 4, the order property already holds, so the new node stays where it is and add stops right away.

Why swimming up is enough

Placing the new node in the next open slot leaves every parent-child edge correct except possibly one: the edge between the new node and its parent. Each swap repairs that edge. When the new node moves up past its parent, the parent moves down into the new node’s old spot. Nothing in the subtree below that spot breaks: the value that moved down was already above that subtree before the swap, so it still has priority at least as high as its new children. The edge from the new node down to its old sibling holds too: the new node outranks the parent it replaced, and that parent already had priority at least as high as the sibling. The only edge that can still be wrong is the new one above, between the new node and its new parent. So we keep comparing upward, one swap at a time, until the new node reaches a parent it does not outrank or becomes the root.

The new node climbs at most from the bottom level to the root, one swap per level. The height of a heap is about $\log n$, which we work out later in the chapter, so add does $O(\log n)$ swaps.