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

#define LEFT(i) (2*(i))
#define RIGHT(i) (2*(i) + 1)

int ASG, CMP;

//Tests if a vector is sorted.
void valid(int n, int a[]){
	int i;
	for(i = 1; i < n; i++)
		if(a[i] > a[i+1]){
			printf("*****ERROR!!!*****");
			break;
		}
}


void gen_avg(int n, int a[]){
	FILE *f = fopen("avg.dat", "a");
	int i;
	fprintf(f, "%d ", n);
	for(i = 1; i <= n; ++i){
		a[i] = rand() % 10000;
		//fprintf(f, "%d ", a[i]);
	}
	fprintf(f, "\n");
	fclose(f);
}


void max_heapify(int a[], int i, int n){

	int aux,largest, l, r;

	largest = i;
	do{
		CMP++;
		i = largest;
		l = LEFT(i);
		r = RIGHT(i);
		if(l <= n && a[i] < a[l])
			largest = l;
		CMP++;
		if(r <= n && a[largest] < a[r])
			largest = r;

		if(largest != i){
			aux = a[i];
			a[i] = a[largest];
			a[largest] = aux;
			ASG += 3;
		}
	} while (i!=largest);
}

void up(int a[], int i){
	int aux;
	while(i > 1 && a[i >> 1] < a[i]){
		aux = a[i];
		a[i] = a[i >> 1];
		a[i >> 1] = aux;
		i >>= 1;
	}
}

void build_max_heap(int a[], int n){
	int i;
	for(i = n/2; i >= 1; i--)
		max_heapify(a, i, n);
}

void build_max_heap2(int a[], int n){
	int i;
	for(i = 2; i <= n; i++)
		up(a, i);
}

void heapsort(int a[], int n){
	int aux, i;
	build_max_heap2(a, n);
	for(i = n; i >= 2; i--){
		aux = a[i];
		a[i] = a[1];
		a[1] = aux;
		ASG+=3;
		max_heapify(a, 1, i-1);
	}
}

int main(){
	int a[500001], n;
	int aux, i, M;

	FILE *f = fopen("algsort.in", "r");
	FILE *g = fopen("algsort.out", "w");

	fscanf(f, "%d", &n);
	for(i = 1; i <= n; ++i)
		fscanf(f, "%d", &a[i]);

	heapsort(a, n);

	for(i = 1; i <= n; ++i)
		fprintf(g, "%d ", a[i]);

	fclose(f);
	fclose(g);
	/*
	FILE *f = fopen("heapsort.csv", "w");
	srand(time(NULL));
	for(M = 100; M <= 100000; M+=300){
	gen_avg(M, a);

	n = M; 
	CMP = ASG = 0;

	heapsort(a, n);
	valid(n, a);
	fprintf(f, "%d, %d, %d, %d\n", n, ASG + CMP, ASG, CMP);
	}
	fclose(f);
	*/
	return 0;
}