Finding a Position in a Linked Heap

LinkedHeap is a binary min-heap built from nodes. Each Node holds a value and two references, left and right. The heap has two fields, root and size. Number the positions of a complete tree in level order, starting from 1 at the root.

Solution

add needs the next open slot and remove needs the last node, but the code only has root and size, and both of those positions are at the bottom of the tree. add also has to swim the new value up, which means moving from a node to its parent, but a Node only references its children.

Solution

$O (n)$ . It visits every node that already has both children, and in a complete tree that is about half of the nodes.

Solution

The next open slot is position 21, which is 10101 in binary. Drop the leading 1 and read 0101 with 0 for left and 1 for right: left, right, left, right.

Following the path costs $O (lo g n)$ . A position up to $n + 1$ has about $lo g_{2} n$ binary digits, and the path takes one step per digit.