Heapsort - building heap

Question

We have to know how to use a heap sort. I can't understand a one thing: when we build a heap, why the size used in loop is divided by 2 (declared as a counter "i")? Below is shown the code. I would be so grateful if anyone would explain it to me.

// heap

void heapify (int tab[], int o, int heapsize)
{
    int l = 2 * o + 1;
    int r = l + 1;
    int largest;

    if (l <= heapsize && tab[o] > tab[l])
        largest = l;
    else
        largest = o;

    if (r <= heapsize && tab[largest] > tab[r])
        largest = r;

    if (largest != o)
    {
        swap(tab[o], tab[largest]);
        heapify(tab, largest, heapsize);
    }
}

void build_heap(int tab[], int heapsize)
{
    for (int i = heapsize/2; i >= 0; i--)
        heapify(tab, i, heapsize);
}

void heap_sort(int tab[], int size)
{
    int heapsize = size;
    build_heap(tab, heapsize);

    do{
        swap(tab[0], tab[heapsize]);
        heapify(tab, 0, heapsize - 1);
        heapsize--;
    } while (heapsize > 0);
}

Answer 1

I assume you mean the line

for (int i = heapsize/2; i >= 0; i--)

Well, what's happening is like this. But first, here's a tip for heaps. You have to constantly switch between the two ways to think about a heap: a contiguous array and a tree.

So if you look at heapify, you can see in the array representation that for index i, the code considers l and r which are 2 * i and 2 * i +. In the tree representation, those are the left and right children.

Now in the heap representation, what is heapsize / 2? It is the part of the penultimate row that actually has children. These children will be considered by the heapify function (we just saw that). There's no point starting to the right of that, since there just aren't children to compare.