Question: What does theSize/2 means in the following code,
Is this somehow related with Insertion O(LogN)?

```
template <class Comparable>
void BinaryHeap<Comparable>::buildHeap( )
{
    for( int i = theSize / 2; i > 0; i-- )
        percolateDown( i );
}

```

For this percolateDown function

```
template <class Comparable>
void BinaryHeap<Comparable>::percolateDown( int hole )
{
  int child;
  Comparable tmp = array[ hole ];

  for( ; hole * 2 <= theSize; hole = child )
  {
    child = hole * 2;
    if( child != theSize && array[child + 1] < array[child])
       child++;
    if( array[ child ] < tmp )
       array[ hole ] = array[ child ];
    else
       break;
  }
  array[ hole ] = tmp;
}

```

Answer: 
A very common representation of a heap is to map it to an array. In this representation, for any node stored at `a[n]` its children are at `a[n*2]` and `a[n*2+1]`. The root node is at `a[1]`.

Given that, dividing the index by two (and discarding any remainder) is simply how you get from the index of a node to the index of its parent.

In the case of `percolateDown` the idea is to start with the nodes one level above the leaves of the heap.

Try searching for "heap in array" for more details.
Ok. It turned out that theSize/2 leads us to the last subtree of unsorted , Binary Heap where we start to percolateDown(i)(sorting function). 

 Then we move to the (i-1)th subtree and percolateDown() that one. And so on Until the Binary Heap Tree is sorted either Max or Min.

It is clarified in this video from time 2:42 (<https://www.youtube.com/watch?v=WsNQuCa_-PU>)