Adding to and Removing from a Heap

The questions in this section use this min-heap, where a smaller value has higher priority:

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

5 goes into the next open slot, the right child of 6:

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

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

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

5 is larger than its new parent 2, so add stops.

Solution

The root 2 is removed, and the last node, 8, moves into the root:

             ╭───╮
             │ 8 │
             ╰─┬─╯
       ┌───────┴───────┐
     ╭─┴─╮           ╭─┴─╮
     │ 4 │           │ 6 │
     ╰─┬─╯           ╰───╯
  ┌────┴────┐
╭─┴─╮     ╭─┴─╮
│ 7 │     │ 9 │
╰───╯     ╰───╯

The smaller child of 8 is 4, and 4 is smaller than 8, so they swap:

             ╭───╮
             │ 4 │
             ╰─┬─╯
       ┌───────┴───────┐
     ╭─┴─╮           ╭─┴─╮
     │ 8 │           │ 6 │
     ╰─┬─╯           ╰───╯
  ┌────┴────┐
╭─┴─╮     ╭─┴─╮
│ 7 │     │ 9 │
╰───╯     ╰───╯

The smaller child of 8 is now 7, and 7 is smaller than 8, so they swap:

             ╭───╮
             │ 4 │
             ╰─┬─╯
       ┌───────┴───────┐
     ╭─┴─╮           ╭─┴─╮
     │ 7 │           │ 6 │
     ╰─┬─╯           ╰───╯
  ┌────┴────┐
╭─┴─╮     ╭─┴─╮
│ 8 │     │ 9 │
╰───╯     ╰───╯

8 is a leaf, so remove stops.

Solution

The child that moves up becomes the parent of the other child. The smaller child is no larger than its sibling, so the order property holds. The larger child would sit above a smaller value and break the order property.