Heap structure in array, computing parent and child

Question

I am studying data structures from Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, and in the section of heapsort it talks about a data structure beneath the algorithm : a heap, that means, a binary tree with all of its levels complete except possibly the lowest, which is filled from the left up to a point.

In this book it says that a common way to represent this data structure is an array, beginning from the index 1 of the array and putting from left to right the first level of the tree, then from left to right the second level of the array and so on. It states that this representation is useful because given a node $n$ of the tree lying in position $A[i]$ of the array, its parent and children can be easily computed as :

Parent = $A[i/2]$

Left child = $A[2i]$

Right child = $A[2i+1]$

I am having a hard time trying to understand why its parent and children are in these positions on the array, could someone give me an intuitive explanation of why this is the case?

• koverman47: I think you mean $Parent = A\lceil i/2\rceil$

Answer 1

While it is possible to write a formal proof, I think the best proof is by picture:

Tree

If you still want a formal proof, here it is. We start by noting that level $d$ of the tree (counting from 0) contains 2ドル^d$ nodes, and so a simple induction shows that level $d$ occupies the indices 2ドル^d, \ldots, 2^{d+1}-1$. Consider now the $i$th node on the $d$th level (again, counting from zero). Its children are nodes 2ドルi,2i+1$ on level $d+1,ドル as the following table makes clear: $$ \begin{array}{c|c} \text{parent} & \text{children} \\\hline 0 & 0,1 \\ 1 & 2,3 \\ 2 & 4,5 \\ \cdots & \cdots \end{array} $$ The index of the $i$th node on the $d$th level is 2ドル^d + i$. The indices of nodes 2ドルi,2i+1$ on level $d+1$ are 2ドル^{d+1}+2i,2^{d+1}+2i+1$. Notice that $$ 2^{d+1}+2i = 2 \times (2^d + i), \\ 2^{d+1}+2i+1 = 2 \times (2^d + i) + 1. $$ This explains the formulas for the left and right children. The formula for the parent follows similarly, since $$ \lfloor (2^{d+1}+2i)/2 \rfloor = \lfloor 2^d + i \rfloor = 2^d + i, \\ \lfloor (2^{d+1}+2i+1)/2 \rfloor = \lfloor 2^d + i + 1/2 \rfloor = 2^d + i. $$