Tracing peek, remove, and add

We continue the trace on the heap that the six add operations built. As before, the value being placed or moved has a dark fill.

peek

The highest-priority element is the root, 1. peek returns it and leaves the tree as it is.

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

remove

The root, 1, is removed. The last node, 7, moves into the root, and its old slot is dropped:

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

The children of 7 are 3 and 5. The smaller child is 3, and 3 outranks 7, so they swap:

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

The children of 7 are now 8 and 4. The smaller child is 4, and 4 outranks 7, so they swap. 7 is now a leaf, so the sink stops:

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

add 2

The next open slot is the one 7 left when it moved to the root, the left child of 5:

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

2 is smaller than its parent, 5, so they swap:

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

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

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

remove

The root, 2, is removed. The last node, 5, moves into the root:

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

The children of 5 are 4 and 3. The smaller child is 3, and 3 outranks 5, so they swap. 5 is now a leaf, so the sink stops:

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

Through all of these operations the tree never grew past three levels.