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:

[code language="C"]
function LEFT(i){
    return 2i;
}
[/code]

[code language="C"]
function RIGHT(i){
    return 2i+1;
}
[/code]

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.