#include <iostream>
using namespace std;
void print_array(int* array, int size);
void build_heap(int* array, int size);
void swap(int& a, int& b);
void heapify(int* array, int node, int size);
void heap_sort(int* array, int size);

void main()
{
	int* array;
	int size;

	cin >> size;
	array = new int[size];

	for (int i=0; i<size; i++)
		array[i] = rand()%100;

	print_array(array, size);
	build_heap(array, size);
	print_array(array, size);
	heap_sort(array, size);
	print_array(array, size);
}

void print_array(int* array, int size)
{
	for (int i=0; i<size;  i++)
		cout << array[i] << " ";

	cout << endl;
}

// build a heap
void build_heap(int* array, int size)
{
	int parent = size / 2 - 1;
	for(parent = size / 2 - 1; parent >=0; parent--)
	{
		heapify(array, parent, size);
	}
}

void swap(int& a, int& b)
{
	int t = a;
	a = b;
	b = t;
}

// make a parent node's value greater than its children
void heapify(int* array, int node, int size)
{
	// is it a leaf?
	if (node > size / 2 - 1)
		return ;

	int left_child = node * 2 + 1;
	int right_child = left_child + 1;
	
	int max = node;
	if (left_child < size && array[left_child] > array[max])
		max = left_child;

	if (right_child < size && array[right_child] > array[max])
		max = right_child;

	// if exchanged, it may affects the 'heap attribute' of its children
	if (max != node)
	{
		swap(array[node], array[max]);
		heapify(array, max, size);
	}
}

// sort. first, build a heap, than, extract the top node.
void heap_sort(int* array, int size)
{
	build_heap(array, size);

	for (int i=size-1; i>0; i--)
	{
		swap(array[i], array[0]);
		heapify(array, 0, i);
	}
}