TAOCP 7.1.3 Exercise 145

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 145. [17] [17] Interpret (137) when h is less than the height of j.

196 COMBINATORIAL SEARCHING 7.1.3

Verified: yes
Solve time: 1m08s

Solution

Let (137) denote the formula in Section 7.1.3 that computes the ancestor of node $j$ at height $h$ in the sideways heap representation. That expression is derived under the implicit condition that the upward traversal from $j$ by $h$ levels remains inside the heap.

The height of a node $j$ in a heap is defined as the number of edges on the path from $j$ to the root. If $h$ is less than this height, then starting at $j$ and moving upward $h$ steps does not reach the root. The computation in (137) therefore performs $h$ valid parent transitions and terminates at an ancestor strictly below the root.

When $h$ is greater than or equal to the height of $j$, repeated application of the parent operation eventually reaches the root and then continues beyond it. In the representation used for sideways heaps, nodes outside the tree are represented by the empty value (or equivalently by $0$ in the bit encoding used in Section 7.1.3). Thus any further application of the parent operation beyond the root remains in this empty state.

When $h$ is less than the height of $j$, the evaluation of (137) does not trigger this overflow beyond the root. The expression therefore retains its intended combinatorial meaning: it returns the unique ancestor of $j$ obtained by moving upward exactly $h$ levels in the heap. No truncation to the root occurs, since the root is not yet reached during the $h$ steps.

Thus (137), interpreted in the case $h < \mathrm{height}(j)$, simply yields the $h$-th ancestor of node $j$ within the tree, with no interaction with the boundary condition at the root.

This completes the solution. ∎