Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
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:
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$.
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?
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.
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.
I really liked Yuval Filmus' answer, but wanted to try explaining it a bit differently after it had clicked for me.
The idea of implementing a full binary tree with an array is essentially just assigning indexes to each node. We'll use 1-indexing, as you'll soon see why, to show that the indexes sneakily encode the normal tree traversal you would use to reach any node.
Normally we start from the root and then go downwards, traveling either left or right. Take the 26th node for example. To reach the 26th node, we take the following path:
root -> right -> left -> right -> left
Now note the binary representation of 26:
26 = 0b1_1010
The initial 1 denotes the root. Afterwards, 0 represents going left while 1 represents going right.
This means that in order to go left we want to append a 0 bit, and to go right we want to append a 1 bit.
In order to achieve this, we left shift one bit (which is multiplying by 2) and then add either 0 or 1.
tree[i].left = tree[2*i] to add a 0 bit.tree[i].right = tree[2*i+1] to add a 1 bit.To use 0-indexing, all we have to do is add 1 everywhere to simulate 1-indexing.
Consider below tree and its array representation.
0
1 2
3 4 5 n
[0, 1, 2, 3, 4, 5, ..., n]
Now element at 0 index has children at indices 1 & 2. Similarly it is true for rest elements as below.
0, 0+1, 0+2
1, 1+2, 1+3
2, 2+3, 2+4
3, 3+4, 3+5
4, 4+5, 4+6
5, 5+6, 5+7
n, n+(n+1), n+(n+2)
Which in tern
n + (n+1) = 2n+1
n + (n+2) = 2n+2
Well, first of all, i_right = i_left + 1. Always. It's obvious, so bellow I'm gonna show only proof of expression i_left_child = i_parent * 2 + 1.
In the explanation bellow there might be quite many definitions like: parent, child, index, position in current level, etc. So instead of greek/latin letters I decided to use the exact numbers from picture, but avoid any math operation on it, like it was a symbol. So it should work with all the numbers.
