Heap structure in array, computing parent and child
While it is possible to write a formal proof, I think the best proof is by picture:



If you still want a formal proof, here it is. We start by noting that level $d$ of the tree (counting from 0) contains $2^d$ nodes, and so a simple induction shows that level $d$ occupies the indices $2^d, \ldots, 2^{d+1}-1$. Consider now the $i$th node on the $d$th level (again, counting from zero). Its children are nodes $2i,2i+1$ on level $d+1$, as the following table makes clear:
$$
\begin{array}{c|c}
\text{parent} &amp; \text{children} \\\hline
0 &amp; 0,1 \\
1 &amp; 2,3 \\
2 &amp; 4,5 \\
\cdots &amp; \cdots
\end{array}
$$
The index of the $i$th node on the $d$th level is $2^d + i$. The indices of nodes $2i,2i+1$ on level $d+1$ are $2^{d+1}+2i,2^{d+1}+2i+1$. Notice that
$$
2^{d+1}+2i = 2 \times (2^d + i), \\
2^{d+1}+2i+1 = 2 \times (2^d + i) + 1.
$$
This explains the formulas for the left and right children. The formula for the parent follows similarly, since
$$
\lfloor (2^{d+1}+2i)/2 \rfloor = \lfloor 2^d + i \rfloor = 2^d + i, \\
\lfloor (2^{d+1}+2i+1)/2 \rfloor = \lfloor 2^d + i + 1/2 \rfloor = 2^d + i.
$$