Let’s assume that each tier of the heap is an array.
T1 ( n0 )
T2 ( n1, n2 )
T3 ( n3, n4, n5, n6 )
T4 (n7, n8, n9, n10, n11, n12, n13, n14)
It may not be clear, but I want you to imagine that $n0$ is the parent of $n1$ and $n2$.
Likewise, $n1$ is the parent of $n3$ and $n4$.
For example, the second tier’s length is $2$.
i.e. $(n1, n2)$
Let’s say $i$ is the global index of the node in question (i.e. the node’s index if the entire tree were to be collapsed within a single array), and
$j$ is the local index of the node, i.e. the index of the node within its tier.
e.g. In the diagram above, if the node in question is $n3$, $i$ is $3$ and $j$ is $0$, because $n3$ is the first element in the 3rd tier.
i = global index of a node n
j = local index of a node n within the tier where the node exists
T = tier
The maximum number of nodes in a certain tier can be expressed by:
$2^T – 1$ // e.g. when you have 3 tiers, you can have at most 7 nodes, as $2 cdot 2 cdot 2 – 1 = 7$
This is because there are $2^{T-1}$ nodes in each tier (note: tier numbering in our example arbitrarily starts from $1$, not $0$) and the sum of powers of $2$ up to $n$ is equal to $2^{n+1} – 1$, as you can see here https://math.stackexchange.com/questions/1990137/the-idea-behind-the-sum-of-powers-of-2
This means that the global index of the last node in the tier is:
$i_{last} = 2^T-1-1$
While the local index of the last node in the tier is:
$j_{last} = 2^{T-1} – 1$ // since there are $2^{T-1}$ elements in tier $T$
We can now compute the global index of the first node in the tier by subtracting the local index of the last node in the tier from its global index:
$i_{first} = i_{last} – j_{last}$
$i_{first} = 2^T – 1 – 1 – j_{last}$
$i_{first} = 2^T – 1 – 1 – (2^{T-1} – 1)$
$i_{first} = 2^T – 2^{T-1} – 1$
$i_{first} = 2*2^{T-1} -2^{T-1} – 1$
$i_{first} = (2 – 1)*2^{T-1} – 1$
$i_{first} = 2^{T-1} – 1$
We can now compute the global index of a node $n$ by adding its local index and the global index of the first node in its tier:
$i = i_{first} + j$
$i = 2^{T-1} – 1 + j$
Let’s now think about the parent of the node in question.
The parent, n', will be in the previous tier, T-1.
The indices in T-1 will be referred to as i', j', i'_first ...
Based on what we’ve shown so far, we can say that the global index of the parent node in the previous tier is:
$i_{first}’ = 2^{T-1-1} – 1$
Now, for every 2 predecessor(left sibling) of the node $n$ in tier $T$ there will be 1 predecessor(left sibling) of parent node $n’$ in $T-1$. Also, given index $j$ in $T$, we know there are $j$ predecessors(left sibling) of $n$ in $T$ – i.e. the index of a node is equal to the number of its predecessors(left sibling). So we can conclude that:
$j’ = floor(j/2)$
Putting it all together, we can conclude that
$i’ = i_f’ + j’$
$i’ = 2^{T-1-1} – 1 + floor(j/2)$
Now let’s rework the previous equation for the global index of parent node $n$, $i = 2^{T-1}-1+j$ to the following:
$i + 1 = 2^{T-1} + j$
Finally, let’s compare that to the equation of the global index of the left-child node:
$begin{align}
i’ &= 2^{T-1-1} – 1 + floor(j/2)\
&= 2^{T-1}/2 + floor(j/2) – 1\
&= floor((2^{T-1} + j)/2) – 1\
&= floor((i + 1)/2) – 1 text{//NOTE: Here we use $i + 1 = 2^{T-1} + j$ mentioned above}\
&= floor((i – 1)/2)\
end{align}$
