We need to prove that in an array representation of heap, the leaves starts at index ⌊n/2⌋+1, ⌊n/2⌋+2 . . .and goes till n, n being the last leaf of the heap.

 

So, to prove it, first we recall that, the LEFT child and the RIGHT child of a node in a heap is given by:
 

function LEFT(i){
    return 2i;
}

 

function RIGHT(i){
    return 2i+1;
}

 


 

Secondly, we also recall that, heaps are almost complete binary tree, meaning, we do not fill right child of any node without filling the left child first.

 


 

Third, realize the mathematical truth that, ⌊n/2⌋ > ( n/2 – 1 )


Now, we are good to go: Lets us take the index of the first leaf node, i.e ⌊n/2⌋+1. For this node, we will attempt to find its left child:

 

LEFT(⌊n/2⌋+1) = 2(⌊n/2⌋+1)

 

Now:

2(⌊n/2⌋+1) > [ 2( n/2-1 + 1) = 2n/2 - 2 + 2 = n ]

 

Therefore:

LEFT(⌊n/2⌋+1) > n

which is greater then the elements of the heap. Therefore ⌊n/2⌋+1 is a leaf and so is the next element, next to next element till n.

 

0 Do You Love This Article ?

CT

Hello All! You are reading the author(s) profile of CorvineLabs Team. We may be 1,2 or ..any in number. Let that remain withing us. You enjoy our write up. If you want to join the team than do Contact Us.

Leave a Reply

Your email address will not be published. Required fields are marked *