Reaching the Parent

The previous section found the path from the root to the next open slot, so add can follow that path down and attach the new node there. Then it has to swim the new value up, and for that it needs a way to get from a node to its parent. A Node only has references to its children.

Ways to reach the parent

Find the parent again from the root. A node’s position tells us its parent’s position: divide by 2. So for each step of the swim, follow the path from the root down to the parent. But each of those traversals costs $O (lo g n)$ , and a swim can take $O (lo g n)$ steps. The whole swim costs $O (lo g^{2} n)$ , a $lo g n$ factor more than it should.
Remember the path. On the way down to the open slot, we pass every ancestor of the new node. Push each one on a stack. Then swim pops them off, one per level. This is $O (lo g n)$ , but it needs a separate stack, filled on every add.
Store a parent reference. Add a parent field to Node, so every node can reach its parent in one step. This is also $O (lo g n)$ . But every node carries one more reference for as long as it is in the heap, and every operation that attaches or detaches a node has to keep that reference correct.

There is a fourth option. In the TreeMap chapter, the recursive put follows the tree down to a null child, creates the new node there, and then, as each call returns, rebalances the node that call is working on. The calls still waiting on the call stack are exactly the ancestors of the new node, from the bottom up. So the work “on the way back up” happens at each ancestor, in order, with no parent references.

add can do the same. Follow the path down recursively. At the open slot, create the new node. Then, as each call returns, compare the node that call was working on with the child it just came back from, and swap if the child outranks it. The call stack holds the path, so we need no separate stack and no parent reference.