Tracing a Heap

Now we run a sequence of operations on a single heap, starting from empty, and draw the tree after every step. The value being placed or moved has a dark fill. This page builds the heap with six add operations. The next page runs peek, remove, and another add on it. The next chapter traces part of this sequence again on its two implementations of the heap.

add 5

The first element becomes the root.

╭───╮
│█5█│
╰───╯

add 8

8 goes in the next open slot, the left child of 5. 8 is larger than 5, so it stays there.

    ╭───╮
    │ 5 │
    ╰─┬─╯
  ┌───┘
╭─┴─╮
│█8█│
╰───╯

add 3

3 goes in the next open slot, the right child of 5:

     ╭───╮
     │ 5 │
     ╰─┬─╯
  ┌────┴────┐
╭─┴─╮     ╭─┴─╮
│ 8 │     │█3█│
╰───╯     ╰───╯

3 is smaller than its parent, 5, so they swap. 3 is now the root, so the swim stops:

     ╭───╮
     │█3█│
     ╰─┬─╯
  ┌────┴────┐
╭─┴─╮     ╭─┴─╮
│ 8 │     │ 5 │
╰───╯     ╰───╯

add 1

The top two levels are full, so the next open slot starts a new level. It is the left child of 8:

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

1 is smaller than its parent, 8, so they swap:

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

1 is smaller than its new parent, 3, so they swap again. 1 is now the root, so the swim stops:

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

add 4

4 goes in the next open slot, the right child of 3. 4 is larger than 3, so it stays there.

             ╭───╮
             │ 1 │
             ╰─┬─╯
       ┌───────┴───────┐
     ╭─┴─╮           ╭─┴─╮
     │ 3 │           │ 5 │
     ╰─┬─╯           ╰───╯
  ┌────┴────┐
╭─┴─╮     ╭─┴─╮
│ 8 │     │█4█│
╰───╯     ╰───╯

add 7

7 goes in the next open slot, the left child of 5. 7 is larger than 5, so it stays there.

               ╭───╮
               │ 1 │
               ╰─┬─╯
       ┌─────────┴─────────┐
     ╭─┴─╮               ╭─┴─╮
     │ 3 │               │ 5 │
     ╰─┬─╯               ╰─┬─╯
  ┌────┴────┐          ┌───┘
╭─┴─╮     ╭─┴─╮      ╭─┴─╮
│ 8 │     │ 4 │      │█7█│
╰───╯     ╰───╯      ╰───╯