# Why does the formula floor((i-1)/2) find the parent 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 index of the parent of element at index i can be found with parent index = floor((i-1)/2)

I have tried to explain why it works. Can anyone help me verify this?

Took reference from Why does the formula 2n + 1 find the child node in a binary heap? thanks to @Giulio

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}