3
$\begingroup$

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

$\endgroup$

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ You made it a zillion times too complicated. $\endgroup$
    – user16034
    Commented Jun 7, 2022 at 14:21
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.