//main.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "heapsort.h"
int read_array(const char *name, double *array, int n);
void rand_array(double *array, int n);
void print_array(double *array, int n);
int f_up(double a, double b);
int f_down(double a, double b);

int f_up(double a, double b)
{
    if( a>b )
        return 1;

    if( a<b )
        return -1;

    return 0;
}

int f_down(double a, double b)
{
    if( a>b )
        return -1;

    if( a<b )
        return 1;

    return 0;
}

/* Предполагается, что n>0 и по указателю array выделена память для n элементов.
 * Ф-ия возвращает:
 * -2, если не удалось прочитать элемент;
 * -1, если не удалось открыть файл;
 * 0, в случае успешного завершения.
 * */
int read_array(const char *name, double *array, int n)
{
    FILE *input;
    int i;

    if( !(input = fopen(name, "r")) )
        return -1;

    for( i = 0; i<n; i++ )
    {
        if( fscanf(input, "%lf", array + i)!=1 )
        {
            fclose(input);
            return -2;
        }
    }

    fclose(input);
    return 0;
}

/* Предполагается, что n>0 и по указателю array выделена память для n элементов. */
void rand_array(double *array, int n)
{
    int i;

    for( i = 0; i<n; i++ )
        array[i] = rand();
}

/* Предполагается, что n>0 и по указателю array выделена память для n элементов.
 * */
void print_array(double *array, int n)
{
    int i;

    if( n>20 )
        n = 20;

    for( i = 0; i<n; i++ )
        printf("Array[%d]=%lf\n", i, array[i]);
}

int main(int argc, const char *argv[])
{
    int n, result_read;
    double *a;
    time_t time_begin;

    if( ((argc!=2) && (argc!=3)) || (sscanf(argv[1], "%d", &n)!=1) || (n<=0) )
    {
        fprintf(stderr, "Usage: %s size_of_array [file_with_array]\t\t([size_of_array]>0)\t(array is random if no file_wint_array)\n", argv[0]);
        return 1;
    }

    if( !(a = (double *)malloc(n*sizeof(double))) )
    {
        fprintf(stderr, "Can not allocate memory!\n");
        return 2;
    }
    // Память выделена

    if( argc==3 )
    {
        result_read = read_array(argv[2], a, n);
        if( result_read<0 )
        {
            switch( result_read )
            {
            case -2:
                fprintf(stderr, "Can not read element from %s\n", argv[2]);
                break;
            case -1:
                fprintf(stderr, "Can not open file %s\n", argv[2]);
                break;
            default:
                fprintf(stderr, "Unknown error %d in file %s\n", result_read, argv[2]);
            }

            free(a);
            return 3;
        }
    } else
    {
        rand_array(a, n);
    }
    // Массив считан или сгенерирован случайный

    printf("Array a[]:\n");
    print_array(a, n);

    time_begin = clock();
    heapsort(a, n, &f_up);
    printf("Time: %.2f seconds\nArray a[]:\n", ( (float)(clock() - time_begin) )/CLOCKS_PER_SEC);
    print_array(a, n);

    free(a);
    return 0;
}



//heapsort.h
#ifndef HEAPSORT_H
#define HEAPSORT_H

void heapsort(double *a, int n, int (*p)(double, double));

#endif



//heapsort.c
#include "heapsort.h"
void swap(double *a, double *b);

/* Предполагается, что n>0, и по указателю a расположен массив из n элементов.
 * Турнирная сортировка или алгоритм heapsort.
 * */
void heapsort(double *a, int n, int (*p)(double, double))
{
    int k, parent, position, i, child_1, child_2, child, width, width_dynamic, num_position;
    double buffer;

    /* Рассматриваем бинарное дерево с корнем a[0], где для любого a[k] потомками являются a[2*k + 1] и a[2*k + 2].
     * Первый этап алгорима: превратить дерево в дерево, в котором всякая цепочка от корня до любого конечного элемента упорядочена по убыванию.
     * */
    for( k = 1; k<n; k++ )
    {
        // Поиск позиции, на которую должен перейти a[k]
        for( position = k; position>0; position = parent )
        {
            parent = (int)( (position - 1)/2 );// Индекс родителя a[position]

            if( p(a[parent],a[k])!=-1 )
                break;
        }

        buffer = a[k];
        for( i = k; i!=position; i = parent )
        {
            parent = (int)( (i - 1)/2 );
            a[i] = a[parent];
        }
        a[position] = buffer;
    }
    // Первый этап закончен. В a[0] находится максимальный элемент.

    /* Второй этап: для всех k = n - 1, .., 1: поменять местами a[0] и a[k], и в массиве первых k элементов массива a восстанавливаем структуру:
     * всякая цепочка от корня до любого конечного элемента упорядочена по убыванию. */
    for( k = n - 1; k>0; k-- )
    {
        swap(a, a + k);

        child_1 = 1;
        child_2 = 2;
        // Поиск позиции, на которую должен перейти a[0] в массиве a длины k
        width = 1;// Число элементов на уровне дерева, на который будет переставлен a[0]
        for( position = 0; position<(k - 1); child_1 = 2*position + 1, child_2 = 2*position + 2)
        {
            if( child_2>k )
            {
                break;
            }

            if( (child_2==k) )
            {
                if( p(a[child_1], a[0])==1 )
                {
                    position = child_1;
                    width *= 2;
                }

                break;
            }

            if( p(a[child_1], a[0])==1 )
            {
                if( p(a[child_2], a[child_1])==1 )
                {
                    position = child_2;
                } else
                {
                    position = child_1;
                }

                width *= 2;
                continue;
            }

            if( p(a[child_2], a[0])==1 )
            {
                if( p(a[child_1], a[child_2])==1 )
                {
                    position = child_1;
                } else
                {
                    position = child_2;
                }

                width *= 2;
                continue;
            }

            break;// (a[position]>=a[child1]) && (a[position]>=a[child2])
        }

        buffer = a[0];
        width_dynamic = width;// Ширина уровня поддерева, в котором находится a[position]
        num_position = position - width + 1;// Номер позиции в уровне поддерева ширины width_dynamic;
        for( i = 0; i<position; i = child, width_dynamic = (int)(width_dynamic/2) )
        {
            if( num_position<(int)(width_dynamic/2) )
            {
                child = 2*i + 1;
            } else
            {
                child = 2*i + 2;
                num_position -= (int)(width_dynamic/2);
            }

            a[i] = a[child];
        }
        a[position] = buffer;
    }
}

void swap(double *a, double *b)
{
    double buffer;

    buffer = *a;
    *a = *b;
    *b = buffer;
}