9
$\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 indicies of the children of element at index n can be found with

$leftchild = 2n + 1$

$rightchild = 2n + 2$

I can see that this formula works and have played around with it for a little bit looking at examples, but I still don't understand why it works. Can anyone help me understand the intuition behind why this is correct?

$\endgroup$
2
  • $\begingroup$ You can think in the nodes grouped in interval of increasing power of 2. i.e. [0] [1, 2] [3,4,5,6] [7,8,9,10,11,12,13,14]... notice that each interval is one level of the tree. And that formula gets you from level $i$ to level $i+1$, mapping each element with two element of the next level exclusively. $\endgroup$ – Marcelo Fornet Jan 22 '18 at 23:43
  • $\begingroup$ @MarceloFornet I don't see how you get to the 2n+1 formula from that though, take for example 5. It has 2 elements to it's left, so in the next level there should be 4 elements to the left of it's first child. So then I would imagine the formula to be my_index + (elements_to_the_left_in_row * 2) + 1 $\endgroup$ – Keatinge Jan 23 '18 at 2:05
6
$\begingroup$

I would like to propose my revisited version of Hiroki's answer. Currently it's been sitting in peer-review (https://cs.stackexchange.com/review/suggested-edits/66932) for a while, so it's not being of use to anyone. Credits to Hiroki for the original answer and structure.

I've simply clarified the math and made every step explicit and chosen a slightly different terminology.


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, $T2$, the second tier, contains nodes $[n1, n2]$ and has length $2$.

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.

For example, in the diagram above, if the node in question is $n3$, $i = 3$ and $j = 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 tree up to a certain tier can be expressed by:

$total\_nodes\_up\_to(T) = 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

Since indexes start from 0, the index of the last node in an array of nodes will be $numNodes - 1$. This means that the global index of the last node in some tier $T$ is:

$i_{last} = total\_nodes\_up\_to(T) - 1 = 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. You can visualize it mentally as "walking backwards" starting from the the last node - if you take local-index-many steps back you land onto the first node in the tier:

$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 first (left) child of the node in question.

The left child, n', will be in the next 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 first node in the next tier is:

$i_{first}' = 2^{T+1-1} - 1 = 2^T - 1$

Now, for each predecessor of the parent node $n$ in tier $T$ there will be 2 predecessors of left-child node $n'$ in $T+1$. Also, given index $j$ in $T$, we know there are $j$ predecessors of $n$ in $T$ - i.e. the index of a node is equal to the number of its predecessors. So we can conclude that:

$j' = 2j$

Putting it all together, we can conclude that

$i' = i_f' + j'$

$i' = 2^T - 1 + 2j$

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 + 2j\\ &= 2*2^{T-1} + 2*j - 1\\ &= 2*(2^{T-1} + j) - 1\\ &= 2*(i + 1) - 1 \text{//NOTE: Here we use $i + 1 = 2^{T-1} + j$ mentioned above}\\ &= 2i + 2 - 1\\ &= 2i + 1\\ \end{align}$

Although the question was why the $2n + 1$ formula works, note that I used $i$ instead of $n$! Let me know if there is anything unclear.

$\endgroup$
1
  • 1
    $\begingroup$ The reason why your edit has remained in review for this long is because it changed the answer quite substantially, so I would either reject it (with reason 'clearly conflicts authors intent') or leave it up to the author (or another reviewer). I've chosen the latter here, although it seems the author also did not make a decision. So I'm making a decision now. The suggested changes are too substantial for an edit, so I suggest you write your own answer, instead (which you did :) ). $\endgroup$ – Discrete lizard May 22 '19 at 16:56
5
$\begingroup$

Just see it as a perfect binary tree, where you have numbered its nodes from root downwards, level by level. What is the relationship between the number you gave an element x and the number that you gave to its children?

Other useful questions: How many nodes are between an element and its children? Why is that? Does it have anything to do with powers of 2, and the tree being a perfect binary tree?

enter image description here

$\endgroup$
4
$\begingroup$

Let's assume that each tier of the heap is an array.

T1 [            0              ]

T2 [     1,            2       ]

T3 [  3,   4,      5,      6   ]

T4 [7, 8, 9, 10, 11, 12, 13, 14]

It may not be clear, but I want you to imagine that $0$ is the parent of $1$ and $2$.

Likewise, $1$ is the parent of $3$ and $4$.

For example, the second tier's length is $2$.

i.e. $[1,2]$

Let's say $i$ is the index of the node in question, and $j$ is the index of the tier.

e.g. In the diagram above, if the node in question $(i)$ is $3$, $j$ is $0$, because $3$ is the first element in the 3rd tier.

i = the index of the heap, indicating the node in question
j = the index of the tier where the node in question 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 put 7 nodes, as $2 \cdot 2 \cdot 2 - 1 = 7$

This means that the index of the node in question looks like...

$i = 2^T-1 - 1 + j$ //This will shortly become "$i + 1 = 2^T-1 + j$"

The first child (left child) of $i$ can be derived by...

$i' = 2^T -1 + 2j$

If you don't see why I multiplied $j$ by 2, I would suggest you draw a map on a paper and see the indexes of $i - 1$'s left and right child.

$\begin{align} i' &= 2^T -1 + 2j\\ &= 2(2^T-1 + j) - 1\\ &= 2(i + 1) - 1 \text{//NOTE: Here we use $i + 1 = 2^T-1 + j$ mentioned above}\\ &= 2i + 2 - 1\\ &= 2i + 1\\ \end{align}$

Although the question was why the $2n + 1$ formula works, note that I used $i$ instead of $n$! Let me know if there is anything unclear.

$\endgroup$
1
  • $\begingroup$ Welcome to Computer Science and thanks for your thorough explanation! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. I've taken the liberty to convert the most important parts in your post to LaTeX, so that it is more nicely formatted. $\endgroup$ – Discrete lizard Mar 17 '18 at 11:30
3
$\begingroup$

Let us consider first the case in which node indices are 1-based (start at 1). The nodes in a heap are arranged so that node $1x_1x_2\ldots x_\ell$ (given in binary) is reached by starting at the root and then:

  • If $x_1 = 0$, choose the left child; if $x_1 = 1$, choose the right child.
  • If $x_2 = 0$, choose the left child; if $x_2 = 1$, choose the right child.
  • ...
  • If $x_\ell = 0$, choose the left child; if $x_\ell = 1$, choose the right child.

This gives a rule for "decoding" any positive integer. This kind of encoding makes it clear that the left child of node number $x$ is $2x$, and the right child of node number $x$ is $2x+1$.

When nodes are 0-based, the formula becomes a bit different. If $y$ is the 0-based address of a node, then $y+1$ is its 1-based address. The 1-based addresses of the children are $2(y+1)$ and $2(y+1)+1$, hence their 0-based addresses are $2(y+1)-1$ and $2(y+1)$, which work out to $2y+1$ and $2y+2$.

$\endgroup$
2
$\begingroup$

Frankly the same question popped up in my head, i tried to do the proof my self at first, but i did not succeed. So i searched for it, and came by this question, but noticed that the top voted solutions had the same ideas as me, so i came back to my ideas and came up with the following solution:

Lets look at an example of a small complete binary tree

Nodes                                   Level   Number of nodes in this level
1                                       1     | 2^0  
2 3                                     2     | 2^1 
4 5 6 7                                 3     | 2^2
8 9 10 11 12 13 14 15                   4     | 2^4

I'm going to use 3 variables to make things shorter: L the level in which a node exists, g the global index of a node, s the subindex of a node in a level (the index of that node in that level). More explanation of these variables will come ahead

Notice that for this whole proof, i'm not starting my indexes at zero but at one to make things easier.

Notice that at each level the number of nodes in that level is 2^(L-1). Also since each level has 2^(L-1) nodes then the index at that level starts at 2^(L-1). Based on the previous info we get that

g = 2^(L-1) + s - 1

so for example the global index of the second node in the third level is

g = 2^(3-1) + 2 - 1 = 4 + 2 + 1 = 5

now lets say we want to get the left child of the node (6), here is what we need to do, we need to walk 1 more step to the end of the current level and then for each node that came before node (6) we need to walk two steps (since each node has 2 children) and then one more step to get to the first (left child).

transforming this into an equation we get

leftChildIndex = parentIndex + (2^(L-1)-s) + 2(s-1) + 1

where (2^(L-1)-s) is the steps that is left to reach the end of current level, and 2(s-1) is 2 steps we need to take for each node that came before the current node.

As an example say we want to get the left child of node (6), this means first we need to move 1 step to reach end of Level 3, then we need to take 4 steps (because of nodes 4,5 having two children's each) and one step.

so for first child of node (6) we get

leftChildIndex = 6 + (2^(3-1) - 3) + 2(3-1) + 1 = 6 + 1 + 4 + 1= 12

so now that we saw the equation works lets get back to it

leftChildIndex = parentIndex + (2^(L-1)-s) + 2(s-1) + 1 = parentIndex + 2^(L-1) - s + 2s  -2 + 1 = parentIndex + 2^(L-1) + s - 1 = parentIndex + g = g + g = 2g

we can replace parentIndex with g so we get leftChildIndex = 2g as expected

I got 2g instead of 2g + 1 because i started my indexes at 1 instead of 0, starting them at zero will get you 2g + 1.

$\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.