Array Implementation of Heap

We have discussed a heap as binary tree. Normal implementation of tree is via pointer, but in heap it is much more efficient to use arrays.

So, suppose we have following heap (having 9 elements) :

Now, we need array of 9 elements.

Now, we see the heap having 3 levels, level 0 as root, and level 3 which is partially filled.

Now, we start putting the elements one by one.
So, level 0 goes at first position, level 2 goes next and so on.

You, might be wondering why we are not wasting any space, and we dont even require pointers. This is coming from properties of almost complete binary tree. For finding parent of the node, we just need

parent(i)
{
   if(i is even)
     return i;
   else
     return floor(i/2);
}

Similarly children of i are:

leftChild(i)
{
   return 2*i;
}

rightChild(i)
{
   return 2*i+1;
}