5
$\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$
  • $\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
4
$\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$

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, 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 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
    $\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 at 16:56
3
$\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$
  • $\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
2
$\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$

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.