Finding the Next Open Slot

Here is the heap after adding 5, 8, 3, 1, 4, and 7, the sequence we traced in the priority queue chapter:

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

The next open slot is the right child of 5.

A level-order search

The tree is complete, so the slots fill in level order: top to bottom, and left to right within each level. The next open slot is the first missing child in level order.

The tree chapter has a traversal that visits nodes in this order. Level-order traversal keeps the nodes waiting to be visited in a queue. It starts with the root in the queue, and then repeats: take a node from the front, visit it, and add its children to the back. To find the open slot, visit each node by checking its children. The first node with a missing child is the parent of the open slot.

This works, but it costs $O (n)$ . The search visits every node that already has both children, and in a complete tree that is about half of the nodes. We want to go straight down one path from the root to the slot. That path is as long as the height of the tree, about $lo g n$ .

The hard part is deciding, at each node, whether to go left or right. Look at the root. The open slot is somewhere below it, but the root’s own children do not say which side it is on. No node stores anything about where it sits in the tree.

Numbering the positions

Number the positions of a complete tree in level order, starting from 1 at the root. A heap of $n$ elements fills positions 1 through $n$ , so the next open slot is always position $n + 1$ . Our heap has 6 elements, so the open slot is position 7:

                ╭───╮
                │ 1 │
                ╰─┬─╯
       ┌──────────┴──────────┐
     ╭─┴─╮                 ╭─┴─╮
     │ 2 │                 │ 3 │
     ╰─┬─╯                 ╰─┬─╯
  ┌────┴────┐           ┌────┴────┐
╭─┴─╮     ╭─┴─╮       ╭─┴─╮     ╭─┴─╮
│ 4 │     │ 5 │       │ 6 │     │█7█│
╰───╯     ╰───╯       ╰───╯     ╰───╯

The children of position $p$ are positions $2 p$ and $2 p + 1$ . For example, the children of 3 are 6 and 7.

Going the other way, divide a position by 2. The quotient is its parent, and the remainder says which child it is: 0 for a left child and 1 for a right child. For example, $7/2 = 3$ remainder $1$ , so position 7 is the right child of position 3.

Repeat the division until you reach the root. Take position 12:

$12/2 = 6$ remainder $0$ , so 12 is the left child of 6.
$6/2 = 3$ remainder $0$ , so 6 is the left child of 3.
$3/2 = 1$ remainder $1$ , so 3 is the right child of 1, the root.

Read the remainders in reverse, 1, 0, 0, and you have the path from the root down to position 12: right, left, left.

For our heap, the open slot is position 7. $7/2 = 3$ remainder $1$ , and $3/2 = 1$ remainder $1$ . The remainders in reverse are 1, 1, so the path is right, then right. From the root, go right to 5, and then right again to the open slot.