Heapsort heapify

Question

I found code for a heapsort from: http://rosettacode.org/wiki/Sorting_algorithms/Heapsort#C

The way I understand it (which is wrong somewhere along the lines) is that the heapsort() function has two loops. The first loop is to create the heap structure (either min or max) and the second loop is to actually sort the doubles. But I think I have the first loop wrong.

The entire code goes like this

#include <stdio.h>
#include <stdlib.h>

#define ValType double
#define IS_LESS(v1, v2)  (v1 < v2)

void siftDown( ValType *a, int start, int count);

#define SWAP(r,s)  do{ValType t=r; r=s; s=t; } while(0)

void heapsort( ValType *a, int count)
{
    int start, end;

    /* heapify */
    for (start = (count-2)/2; start >=0; start--) {
        siftDown( a, start, count);
    }

    for (end=count-1; end > 0; end--) {
        SWAP(a[end],a[0]);
        siftDown(a, 0, end);
    }
}

void siftDown( ValType *a, int start, int end)
{
    int root = start;

    while ( root*2+1 < end ) {
        int child = 2*root + 1;
        if ((child + 1 < end) && IS_LESS(a[child],a[child+1])) {
            child += 1;
        }
        if (IS_LESS(a[root], a[child])) {
            SWAP( a[child], a[root] );
            root = child;
        }
        else
            return;
    }
}


int main()
{
    int ix;
    double valsToSort[] = {
        1.4, 50.2, 5.11, -1.55, 301.521, 0.3301, 40.17,
        -18.0, 88.1, 30.44, -37.2, 3012.0, 49.2};
#define VSIZE (sizeof(valsToSort)/sizeof(valsToSort[0]))

    heapsort(valsToSort, VSIZE);
    printf("{");
    for (ix=0; ix<VSIZE; ix++) printf(" %.3f ", valsToSort[ix]);
    printf("}\n");
    return 0;
}

My question is, why does the /heapify/ loop start at (count-2)/2?

the snippet from heapsort() here:

    /* heapify */
    for (start = (count-2)/2; start >=0; start--) {
        siftDown( a, start, count);
    }

UPDATE

I think I may have just answered my own question, but is it because we have to establish a heap structure, where the loop's partial focus is on creating a balanced tree? That is, heaps have to have every level filled except for the last one. Is this correct thinking?

Answer 1

For odd count, the first child pair for heapify is a[((count-2)/2)*2 + 1] and a[((count-2)/2)*2 + 2], the last two elements of the array. For even count, the solo child is at a[((count-2)/2)*2 + 1], the last element of the array. This is the starting point to heapify the entire array. The second loop only has to re-heapify a mostly heapfied array[0 to end] as end decreses.

Wiki article:

http://en.wikipedia.org/wiki/Heapsort