TAOCP 7.1.3 Exercise 144
In a sideways heap, nodes are indexed so that each node $j \ge 2$ has a unique parent $k = \lfloor j/2 \rfloor$, and the two children of $k$ are $2k$ and $2k+1$ as in the binary-heap structure describ...
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 144. [16] [16] What node is the sibling of node j in a sideways heap? (See (134).)
Verified: yes
Solve time: 1m03s
Solution
In a sideways heap, nodes are indexed so that each node $j \ge 2$ has a unique parent $k = \lfloor j/2 \rfloor$, and the two children of $k$ are $2k$ and $2k+1$ as in the binary-heap structure described in (134).
Let $j \ge 2$ and write $j$ in one of the two forms $j = 2k$ or $j = 2k+1$. In the first case, $j = 2k$ is the left child of $k$, and the other child of $k$ is $2k+1 = j+1$. In the second case, $j = 2k+1$ is the right child of $k$, and the other child is $2k = j-1$. Thus the sibling of $j$ is obtained by toggling the least significant binary digit of $j$.
If $j = 2k$, then $j = (,\ldots 0,)_2$ and its sibling is $2k+1 = (,\ldots 1,)_2$. If $j = 2k+1$, then $j = (,\ldots 1,)_2$ and its sibling is $2k = (,\ldots 0,)_2$. In both cases, this operation is exactly the bitwise exclusive-or with $1$, giving the sibling as $j \oplus 1$.
The root node $j = 1$ has no parent and therefore no sibling in this indexing scheme.
Therefore the sibling of node $j$ in a sideways heap is
$$ \boxed{j \oplus 1 \text{ for } j \ge 2}. $$