A Heap in an Array

LinkedHeap meets the costs set in the priority queue chapter: peek is $O(1)$, and add and remove are $O(\log n)$. But some of that work has nothing to do with the heap’s order.

• Reaching the bottom of the tree. Every add and every remove writes a position in binary and traverses from the root to the bottom, about $\log n$ steps, before any swim or sink starts. Even an add whose value never moves up still does that traversal.
• Getting back up. A node has no reference to its parent. add handles that with recursion, so the call stack holds the path, about $\log n$ frames, while it runs.
• Memory. Each element is stored in its own Node object, with two references, left and right.

All three costs come from the representation. A linked tree is built to hold any shape, and we follow its references because we cannot predict the shape. A heap’s shape is not like that. It is always a complete tree, so for every size $n$ there is exactly one shape. Position 7 is always the right child of position 3, and the last node is always position $n$. So we can drop the nodes and store the tree as a plain array, with no node objects and no child references at all.

The idea is to reuse the position numbering from finding the next open slot: number the nodes in level order, top to bottom, and left to right within each level. There we started at 1 at the root. An array starts at index 0, so here we start at 0. Take this heap:

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

Number its nodes in level order, starting from 0:

               ╭───╮
               │ 0 │
               ╰─┬─╯
       ┌─────────┴─────────┐
     ╭─┴─╮               ╭─┴─╮
     │ 1 │               │ 2 │
     ╰─┬─╯               ╰─┬─╯
  ┌────┴────┐          ┌───┘
╭─┴─╮     ╭─┴─╮      ╭─┴─╮
│ 3 │     │ 4 │      │ 5 │
╰───╯     ╰───╯      ╰───╯

Now store each value in the array slot with its number:

  0   1   2   3   4   5
  ↓   ↓   ↓   ↓   ↓   ↓
┌───┬───┬───┬───┬───┬───┐
│ 1 │ 3 │ 5 │ 8 │ 4 │ 7 │
└───┴───┴───┴───┴───┴───┘

As with the positions, a heap of $n$ elements fills indices 0 through $n-1$ with nothing skipped, so the array has no gaps. A tree that is not complete would leave gaps.

The array is not sorted, unlike the sorted-array design in the priority queue chapter. Reading it from left to right goes through the tree level by level, not in priority order.

Finding a parent and a child by index

In this layout, we move between a node and its children with arithmetic.

A node at index $i$ has its children at

$$\text{left child}=2i+1,\text{right child}=2i+2.$$

Check it: node 0 gives children 1 and 2, node 1 gives 3 and 4, and node 2 gives 5 and 6 (6 is past the end here, so node 2 has only a left child).

These are the formulas from finding the next open slot, $2p$ and $2p+1$, with every number one smaller: index $i$ is position $i+1$, so the children at positions $2(i+1)$ and $2(i+1)+1$ are at indices $2i+1$ and $2i+2$.

Going the other way, the parent of a node at index $j$ is

$$\text{parent}=\frac{j-1}{2},$$

using integer division, which drops any remainder. Check it: node 3 gives $(3-1)/2=1$, node 4 gives $(4-1)/2=1$ once the remainder is dropped, so both point back to node 1, and node 5 gives $(5-1)/2=2$.

No node objects and no references

This removes the traversals from the root and the references listed above. The two slots that the linked heap reached by traversing from the root are now at known indices:

• add puts the new element in the next open slot, which is just the end of the array, index $n$.
• remove works with the last node, the slot just before the end, index $n-1$.

Both are found by arithmetic, in $O(1)$, without traversing the structure.