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

void heapify(int *heap, int elements);
void interSchimba(int *heap, int index1, int index2);
void shiftDown(int *heap, int root, int elements);
void heapSort(int *heap, int elements);

int main() {
    int n, numbers[500001], i;
    FILE *input = fopen("algsort", "r");
    if(input == NULL) {
        perror("Nu se poate deschide fisierul ");
        exit(1);
    }

    fscanf(input, "%d", &n);
    //numbers = (int*)calloc(n, sizeof(int));

    for(i = 0; i < n; ++i)
        fscanf(input, "%d", &numbers[i]);
    heapSort(numbers, n);

    fclose(input);
    input = fopen("algsort.out", "w");

    for(i = 0; i < n; ++i)
        fprintf(input, "%d ", numbers[i]);

    fclose(input);
    return 0;
}

void heapify(int *heap, int elements) {
    int actual = (elements - 1) / 2;

    while(actual >= 0) {
        shiftDown(heap, actual, elements - 1);
        --actual;
    }
}

void interSchimba(int *heap, int index1, int index2) {
    int temp;
    temp = heap[index1];
    heap[index1] = heap[index2];
    heap[index2] = temp;
}

void shiftDown(int *heap, int root, int elements) {
    int toSwap, child;

    while(root *2 + 1 <= elements) {
        child = root * 2 + 1;
        toSwap = root;
        if(heap[toSwap] < heap[child])
            toSwap = child;
        if(child + 1 <= elements && heap[toSwap] < heap[child + 1])
            toSwap = child + 1;
        if(toSwap != root) {
            interSchimba(heap, toSwap, root);
            root = toSwap;
        }
        else return;
    }
}

void heapSort(int *heap, int elements) {
    heapify(heap, elements);

    --elements;
    while(elements > 0) {
        interSchimba(heap, 0, elements);
        --elements;
        shiftDown(heap, 0, elements);
    }
}