Why does the formula 2n + 1 find the child node in a binary heap?

I learned that when you have a binary heap represented as a vector / list / array with indicies [0, 1, 2, 3, 4, 5, 6, 7, 8, ...] the indicies of the children of element at index n can be found with

$leftchild = 2n + 1$

$rightchild = 2n + 2$

I can see that this formula works and have played around with it for a little bit looking at examples, but I still don't understand why it works. Can anyone help me understand the intuition behind why this is correct?

Let us consider first the case in which node indices are 1-based (start at 1). The nodes in a heap are arranged so that node $1x_1x_2\ldots x_\ell$ (given in binary) is reached by starting at the root and then:

• If $x_1 = 0$, choose the left child; if $x_1 = 1$, choose the right child.

• If $x_2 = 0$, choose the left child; if $x_2 = 1$, choose the right child.

• ...

• If $x_\ell = 0$, choose the left child; if $x_\ell = 1$, choose the right child.

This gives a rule for "decoding" any positive integer. This kind of encoding makes it clear that the left child of node number $x$ is $2x$, and the right child of node number $x$ is $2x+1$.

When nodes are 0-based, the formula becomes a bit different. If $y$ is the 0-based address of a node, then $y+1$ is its 1-based address. The 1-based addresses of the children are $2(y+1)$ and $2(y+1)+1$, hence their 0-based addresses are $2(y+1)-1$ and $2(y+1)$, which work out to $2y+1$ and $2y+2$.

StackExchange Computer Science Q#87154, answer score: 8