#include <stdio.h>

void swap(int* data, unsigned int i, unsigned int j) {
    int tmp = data[i];
    data[i] = data[j];
    data[j] = tmp;
}

void siftdown(int* data, unsigned int n, unsigned int i) {
    unsigned int left, right, ip;
    while( i < n ) {
        left = 2 * i + 1;
        right = 2 * i + 2;
        if( !(left < n) ) break;

        ip = left;

        if( right < n && data[ip] < data[right] ) ip = right;
        if( data[ip] < data[i] ) break;

        swap(data,i,ip);
        i = ip;
    }
}

void heapcreate(int* data, unsigned int n) {
    for(unsigned int i = n/2; i > 0; i--) {
        siftdown(data, n, i);
    }
    siftdown(data, n, 0);
}

void heapsort(int* data, unsigned int n) {
    heapcreate(data, n);
    for(unsigned int heapsize = n-1; heapsize > 0; heapsize--) {
        swap(data,0,heapsize);
        siftdown(data,heapsize,0);
    }
}

int main( int argc, char *argv[] ) {
    int data[10] = { 3,7,5,1,2,8,9,0,4,6 };
    heapsort(data, 10);

    for(unsigned int i = 0; i < 10; i++) printf("%d ", data[i]);
    printf("\n");

	return 0;
}