#include <iostream>
using namespace std;

void heapSort(int arr[], int n)
{

	for (int j = 0; j < n; j++)
	{
		for (int i = n / 2 - 1 - j / 2; i > -1; i--)
		{
			if (2 * i + 2 < n - 1 - j)
			{
				if (arr[2 * i + 1] > arr[2 * i + 2])
				{
					if (arr[i] < arr[2 * i + 1])
					{
						swap(arr[i], arr[2 * i + 1]);
					}
				}
				else
					if (arr[i] < arr[2 * i + 2])
					{
						swap(arr[i], arr[2 * i + 2]);

					}
			}
			else
				if (2 * i + 1 <= n - 1 - j)
					if (arr[i] < arr[2 * i + 1])
						swap(arr[i], arr[2 * i + 1]);
		}
		swap(arr[0], arr[n - 1 - j]);
	}
}



int main()
{
	int a[] = { 5,4,9,1,3,2,12,7,6,8 };
	for (int i = 0; i < 10; i++)
		cout << a[i] << ' ';
	cout << endl;
	heapSort(a, 10);
	for (int i = 0; i < 10; i++)
		cout << a[i] << ' ';
	return 0;
}