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

typedef int int_array_type[10];

static inline int get_left_child_index(int index)
{
    return (index << 1) + 1;
}

static inline int get_right_child_index(int index)
{
    return (index << 1) + 2;
}

void fill_array(int_array_type array)
{
    int i;
    for(i = 0; i < sizeof(int_array_type)/sizeof(array[0]); i++)
        array[i] = rand() % 100;
}

void print_array(int_array_type array)
{
    int i;
    for(i = 0; i < sizeof(int_array_type)/sizeof(array[0]); i++)
        printf("%d ", array[i]);
    printf("\n");
}

void swap(int *first, int *second)
{
    int tmp = *first;
    *first = *second;
    *second = tmp;
}

void heapify(int_array_type array, int index, unsigned int size)
{
    int left = get_left_child_index(index);
    int right = get_right_child_index(index);
    int largest = index;

    if(left <= size)
        if(array[left] > array[index])
            largest = left;
    if(right <= size)
        if(array[right] > array[largest])
            largest = right;
    if(largest != index){
        swap(&array[index], &array[largest]);
        heapify(array, largest, size);
    }
}

void build_heap(int_array_type array)
{
    int i;
    const int number_of_elements = sizeof(int_array_type)/sizeof(*array);
    for(i = number_of_elements/2; i >= 0; i--)
        heapify(array, i, number_of_elements);
}

void heapsort(int_array_type array)
{
    int last_index = sizeof(int_array_type)/sizeof(*array);
    //int last_index = sizeof(int_array_type)/sizeof(*array-1);

    int i;

    build_heap(array);
    for(i = last_index; i > 0; i--){
        swap(&array[0], &array[i]);
        heapify(array, 0, --last_index);
    }
}

int main(void)
{
    srand(time(NULL));
    int_array_type array;
    fill_array(array);
    print_array(array);
    printf("\n");
    heapsort(array);
    print_array(array);
    return 0;
}