Tracing a Heap

The question in this section is about a priority queue implemented as a min-heap, where a smaller value has higher priority.

Exercise

Start from an empty min-heap and perform the following operations in order. Draw the tree after each one, and give the value peek returns.

add 6, add 9, add 4, add 7, add 2, peek, remove, add 5, remove

Solution

add 6:

╭───╮
│ 6 │
╰───╯

add 9: it goes under 6 on the left and stays.

    ╭───╮
    │ 6 │
    ╰─┬─╯
  ┌───┘
╭─┴─╮
│ 9 │
╰───╯

add 4: it goes under 6 on the right and swaps with 6.

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

add 7: it goes under 9 on the left and swaps with 9.

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

add 2: it goes under 7 on the right, swaps with 7, then swaps with 4.

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

peek: returns 2. The tree does not change.

remove: 2 is removed. 7 moves into the root and swaps with 4.

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

add 5: it goes under 7 on the right and swaps with 7.

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

remove: 4 is removed. 7 moves into the root and swaps with 5.

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