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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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