Tracing a Recursive add

In the priority queue chapter, we traced a sequence of operations on a heap. After adding 5, 8, 3, 1, 4, and 7 and removing once, the heap looked like this:

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

The next operation was add 2. The illustrations show only the values.

Going down the path

add grows the size from 5 to 6, so the new element goes at position 6. That is 110 in binary. Drop the leading 1, and the path is 10: right, then left.

The call on the root, which holds 3, reads 1 and calls itself on 3.right. The call on the node holding 5 reads 0 and calls itself on 5.left. That reference is null, and the path has no bits left, so the call on 5.left is the base case: it creates the new node and returns it.

call stack

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ add(node=null)                        ┃
        ┃   return new Node(2)  (the open slot) ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
        ┌───────────────────────────────────────┐
        │ add(node=5)                           │
        │   waiting for add(5.left)             │
        ├───────────────────────────────────────┤
        │ add(node=3)                           │
        │   waiting for add(3.right)            │
        └───────────────────────────────────────┘

tree

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

The two waiting calls are the ancestors of the open slot, from the parent at the top of the stack to the root at the bottom. They are the nodes the new value may swim past.

Unwinding, one swim step per call

The call on the node holding 5 receives the new node and stores it with 5.left = <new node>. Then it calls swimStep. The child holds 2, which outranks 5, so the two values swap. The call returns its node.

call stack

        ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
top ──▶ ┃ add(node=3)                ┃ ◀── receives the node now holding 2
        ┃   waiting for add(3.right) ┃
        ┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛

tree

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

The call on the root receives that node and stores it with 3.right = <node>. That is the same node 3.right already pointed to. Only its value changed. Then swimStep compares the child, now holding 2, with the root, holding 3. 2 outranks 3, so they swap. The call returns the root, and the public method stores it in root.

call stack

        (empty — all calls have returned)

tree

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

This is the same heap the priority queue chapter’s trace reached after add 2.