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

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

void siftdown(int* data, size_t n, size_t i) {
    while(2*i+1<n) {
        if(2*i+2>=n) {
            if(data[i] < data[2*i+1]) {
                swap(data, i, 2*i+1);
                i = 2*i+1;
            } else {
                break;
            }
        } else {
            if(data[i] < data[2*i+1] && data[2*i+1] > data[2*i+2]) {
                swap(data, i, 2*i+1);
                i = 2*i+1;
            } else if(data[i] < data[2*i+2]) {
                swap(data, i, 2*i+2);
                i = 2*i+2;
            } else {
                break;
            }
        }
    }
}

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

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

int main( int argc, char *argv[] ) {

    int n = 1000;
    if(argc > 1) n = atoi(argv[1]);
    srand(time(NULL));
    int* data = malloc(sizeof(int)*n);
    for(size_t i = 0; i < n; i++) {
        data[i] = rand();
    }
    heapsort(data,n);
    int prev = data[0];
    for(size_t i = 1; i < n; i++) {
        assert(prev <= data[i]);
        prev = data[i];
    }
	return 0;
}