#include <iostream>
#include <ctime>
using namespace std;

const int n = 100;
int a[n];
int heap_size = n;

void heapify(int i)
{
	int m = i;
	if (2 * i + 1 < heap_size && a[2 * i + 1] > a[m]) m = 2 * i + 1;
	if (2 * i + 2 < heap_size && a[2 * i + 2] > a[m]) m = 2 * i + 2;
	if (m != i) { swap(a[i], a[m]); heapify(m); }
}

void heap_sort()
{
	for (int i = n / 2 - 1; i >= 0; i--) heapify(i); // build heap
	for (int i = n - 1; i >= 1; i--){ swap(a[0], a[i]); heap_size--; heapify(0); }
}

int main()
{
	srand(time(NULL));
	for (int i = 0; i < n; i++)a[i] = rand() % 100000;

	heap_sort();
	for (int i = 0; i < n; i++)cout << a[i] << " ";
	cout << endl;

	return 0;
}