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

void heapSort(double* a, int n);
void sieve(double *a, int n, int i);
void swap(double *p, double *q);

int main() {
    int n, i;
    double *a = NULL;
    while (true) {
        printf("n:\n");
        if (scanf("%d", &n) < 1 || n <= 0)
            break;

        delete[] a;
        a = new double[n];

        for (i = 0; i < n; ++i) {
            a[i] = (double)(rand() % 100);
        }

        for (i = 0; i < n; ++i) {
            printf("%5.1lf", a[i]);
            if ((i+1) % 10 == 0)
                printf("\n");
        }
        printf("\n====\n");

        heapSort(a, n);

        printf("Sorted:\n");

        for (i = 0; i < n; ++i) {
            printf("%5.1lf", a[i]);
            if ((i+1) % 10 == 0)
                printf("\n");
        }
        printf("\n====\n");
    }

    delete[] a;
    return 0;
}

void heapSort(double* a, int n) {
    // 1. Building of binary heap
    int k = n/2;
    while (k > 0) {
        // Invariant: a[k], a[k+1], ..., a[n-1] is a heap
        --k;
        sieve(a, n, k);
    }

    // 2. Sorting by heap
    k = n;
    while (k > 1) {
        // Invariant: a[0], a[1], ..., a[k-1] is a heap,
        // a[k] <= a[k+1] <= ... <= a[n-1]
        // a[i] <= a[k] when i < k
        --k;
        swap(&(a[0]), &(a[k]));
        sieve(a, k, 0);
    }
}

void sieve(double *a, int n, int i) {
    while (true) {
        int s0 = 2*i;    // Left son of node i
        if (s0 >= n)
            break;       // Node i has no children (terminal node)
        int s1 = s0 + 1; // Right son of i
        int s = s0;
        if (s1 < n && a[s1] > a[s0])
            s = s1;      // Elder son of i
        if (a[i] >= a[s])
            break;       // Node i is already in its place
        swap(&(a[i]), &(a[s])); // Swap node i with its elder son
        i = s;                  // Go down the tree
    }
}
        
void swap(double *p, double *q) {
    double tmp = *p;
    *p = *q; *q = tmp;
}