// heap.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <fstream>

using namespace std;
void citire(int heap[], int& n) {

	ifstream fin("algsort.in");
	fin >> n;
	
	for (int i = 1; i <= n; i++) {
		fin >> heap[i];

	}

	
}
int left_son(int k) {
	return k * 2;
}
int right_son(int k) {
	return k * 2 + 1;
}
int father(int k) {
	return k / 2;
}
void sift(int heap[], int n, int k) {
	int son;
	do {
		son = 0;
		if (left_son(k) <= n) {
			son = left_son(k);

			if (right_son(k) < n && heap[right_son(k)] > heap[son]) {
				son = right_son(k);
			}
			if (heap[son] <= heap[k]) {
				son = 0;
			}
		}
		if (son) {
			swap(heap[son], heap[k]);
			k = son;
		}
		
	} while (son);
}
void heap_sort(int heap[], int n) {
	for (int i = n; i >= 2; i--) {
		swap(heap[i], heap[1]);
		sift(heap, i - 1, 1);
	}
}
void build_heap(int heap[], int n) {
	for (int i = n / 2; i > 0; i--) {
		sift(heap, n, i);
	}
}
int main()
{
	int* heap = new int[500001];
	cout << "sal";
	int n;
	citire(heap, n);
	build_heap(heap, n);
	heap_sort(heap, n);
	ofstream fout("algsort.out");
	for (int i = 1; i <= n; i += 1) {
		fout << heap[i] << " ";
	}
  
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file