// Heapsort Algorithm
// M.Menault 2024

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

void print_array(int* array, int length)
{
    static int count = 0;
    int i = 0;
    printf("(%3.3d) Array : ",count++);
    for(i=0; i < length; i++)
    {
        printf("%5d ",array[i]);
    }
    printf("\n");
}

void sift(int* array, int node, int length)
{
    int largest_node = node;
    int left_node = 2*node+1;
    int right_node = 2*node+2;
    int temp_value = 0;

    if(left_node < length && array[left_node] > array[largest_node])
    {
        largest_node = left_node;
    }

    if(right_node < length && array[right_node] > array[largest_node])
    {
        largest_node = right_node;
    }

    if(largest_node != node)
    {
        temp_value = array[node];
        array[node] = array[largest_node];
        array[largest_node] = temp_value;
        sift(array,length,largest_node);
    }
}
 
void heapsort(int* array, int length)
{
    int i = 0;
    int temp_value = 0;
 
    // Sift the current array (binary tree)
    for(i=(length/2); i >= 0; i--)
    {
        sift(array,i,length);
    }
    // Heapsort !
    for(i=length-1; i > 0; i--)
    {
        temp_value = array[i];
        array[i] = array[0];
        array[0] = temp_value;
        sift(array,0,i);
    }
}
 
void generate_array(int* array, int length)
{
    int i = 0;
    static int first_call = 1;

    if(first_call)
    {
	first_call = 0;
        srand(time(NULL));
    }
    for(i=0; i < length; i++)
    {
        array[i] = rand() % 20 + 1;
    }
}