How to prove that children in heap data structure are located at: 2*n and 2*n+1?

Question

This is not homework question, I today learned heap data structure and I don't know how would I prove that relation is true. Thanks.

Answer 1

Prove by Induction:

1. children of root (1) -> child1= 2*1=2 , child2= 2*1 + 1 = 3 true
2. Assuming children of kth element are -> child1= 2k , child2=2k+1
3. Prove children of (k+1)th elements are child1= 2*(k+1), child2=2(k+1) + 1 (Prove this)

Proof of 3: since children of kth elements are at 2k and 2k+1 (based on assumption) then, next two elements after are 2k+2 and 2k+3.

2k+2 = 2(k+1) (first child for k+1 is proved)(a)

2k+3 = 2k + 2 + 1 = 2(k+1) + 1 (second child for k+1 is proved)(b)

from (a) & (b) --> thus 3 is valid thus child of element n are 2n and 2n+1

Answer 2

Here is a proof without induction, which is more intuitive and insightful from my point of view. Here are 4 mental steps that proof this relation to me.

Flatten the tree.

Let's enumerate all the vertices of a tree in the following way:

Here is how these verices will look in array:

Segregate siblings in array.

We can notice that every two consecutive nodes (except the first one) are children of some common vertex:
1 [ 2 3 ] [ 4 5 ] [ 6 7 ] [ 8 9 ]

Build this array differently.

Now let's think in reverse order. What if we have an array of pairs: [(2, 3), (4 5), (6, 7), (8, 9)] and we want to aggregate them in a single array?

Let's say we have already placed the first 3 pairs:
[ 2 3 ] [ 4 5 ] [ 6 7 ]

What will be the index of the number 8 in the final array? We know that we have placed 3 pairs already and they have taken 3 * 2 = 6 places in the beginning, so we will take the 7'th place.

If we code the placement of pairs, it will look like that:

pair<int, int> pairs[4] = { {2, 3}, {4, 5}, {6, 7}, {8, 9} };
int aggregate[2 * 4];
for (int i = 0; i < 4; i++)
{
    aggregate[2 * i] = pairs[i].first;
    aggregate[2 * i + 1] = pairs[i].second;
}

The key part is this index of array aggregate[2 * i]. In this code it is obvious to see why we multiply by 2 — we do it, because we have to skip the previous i - 1 pairs.

Combine flattening of tree and aggregation of pairs

Now we need to see the correspondance between building aggregate array of pairs and flattening of a binary tree. Every pair of siblings has a parent. If two siblings (2, 3) and (4, 5) are adjacent in array, then theirs parents are also adjacent. Siblings (2, 3) have parent 1, siblings (4, 5) have parent 2, siblings (6, 7) have parent 3. So the parent is like an index in this array of pairs pairs[4] = { (2, 3), (4, 5), (6, 7), (8, 9) } and when we use 2 * i to access its left child, we can think of skipping i - 1 pairs of children generated by previous vertices.