Why does the formula floor((i-1)/2) find the parent node in a binary heap?

Question

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

Answer 1

Levels by levels, the indexes of a binary heap are

$$0\\1\ \ \ \ \ \ \ \ \ \ \ \ \ 2\\3\ \ \ \ \ \ 4\ \ \ \ \ \ 5\ \ \ \ \ \ 6\\7\ 8\ 9\ 10\,11\,12\,13\,14\\\cdots$$

and it is rather clear that the sons of $n$ are $2n+1$ and $2n+2$.

By inversion, the father of $m$ is one of $\dfrac{m-1}2$ or $\dfrac{m-2}2$, and more precisely the one that is an integer.

Answer 2

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}$

Answer 3

If you look at the indices of nodes in a binary heap, left child index is always an odd number, and right is always even.

e.g.

# I made the values match the indices for simplicity
[0,1,2,3,4,5,6]

   0
  / \
 1   2
/ \ / \
3 4 5 6

For parent 1, left is index 3 and right is index 4 (odd and even). Similarly, for parent 2, left is 5 and right is 6 (odd and even).

Formulae for the left and right children are (assume i is the index of the parent node):

left = 2 * i + 1
right = 2 * i + 2

Using simple algebra, we can say that i = (left - 1) / 2 = (right - 2) / 2:

left = 2 * i + 1
left - 1 = 2 * i + 1 - 1
left - 1 = 2 * i
(left - 1) / 2 = i

right = 2 * i + 2
right - 2 = 2 * i + 2 - 2
right - 2 = 2 * i
(right - 2) / 2

So we have two formulae for computing the parent from either the left or the right child. We also know that right is always even. This means right - 1 will always be odd, and that dividing it by 2 will result in some fraction as opposed to a whole number. Therefore, we can apply the formula for getting the left child's parent to the right child as long as we get the floor of (right - 1) / 2. It'll work for the left child because the floor of a whole number is the whole number itself. It'll also work for the right child because the floor of a fraction is just its lower bound.