#include<iostream>
using namespace std;

void afisare(int v[], int n)
{
	int i;
	for (i = 0; i < n; i++)
		cout << v[i] << " ";
	cout << endl;
}

void ConstructionBottomUp(int v[],int n)
{
	int i, j, k, value;
	bool heap;
	for (i = n / 2 - 1 ; i >= 0; i--)
	{
		k = i;
		value = v[k];
		heap = false;
		while (!heap && 2 * k + 1 <= n)
		{
			j = 2 * k + 1;
			if (j < n)
				if (v[j] < v[j + 1])
					j++;
			if (value >= v[j])
				heap = true;
			else
			{
				v[k] = v[j];
				k = j;
			}
		}
		v[k] = value;
	}
}

void heapify(int v[], int n, int i)
{
	int left, right,aux,max;
	left = 2 * i + 1;
	right = 2 * i + 2;
	if (left < n && v[left] > v[i])
		max = left;
	else
		max = i;
	if (right < n && v[right] > v[max])
		max = right;
	if (max != i)
	{
		aux = v[i];
		v[i] = v[max];
		v[max] = aux;
		heapify(v, n, max);
	}

}

void maxHeap(int v[], int n)
{
	int i;
	for (i = n / 2 - 1; i >= 0; i--)
		heapify(v, n, i);
}

void heapSort(int v[], int n)
{
	maxHeap(v, n);
	int i,aux;
	for (i = n - 1; i >= 0; i--)
	{
		aux = v[0];
		v[0] = v[n - 1];
		v[n - 1] = aux;
		n--;
		afisare(v, n);
		heapify(v, i, 0);
	}
}

void ConstructionTopDown(int v[], int n,int w[],int &m)
{
	int i, aux,j;
	bool heap;
	w[m] = v[0];
	m++;
	for (i = 1; i < n; i++)
	{
		w[m] = v[i];
		m++;
		heap = false;
		j = i;
		while (!heap && j > 0)
		{
			if (w[j] >  w[(j - 1) / 2])
			{
				aux = w[j];
				w[j] = w[(j - 1) / 2];
				w[(j - 1) / 2] = aux;
			}
			else
			{
				heap = true;
			}
			j = (j / 2) - 1;
		}
	}
}

int main()
{
	/*int v[] = { 25,57,48,37,12,92,86,33 };
	int n = 8;
	afisare(v, n);
	ConstructionBottomUp(v, n);
	afisare(v, n);
	int v[] = { 2,8,5,3,9,1 };
	int n = 6;
	afisare(v, n);
	heapSort(v, n);
	afisare(v, n);*/
	int v[] = { 4,7,12,3,18,9 };
	int n = sizeof(v) / sizeof(v[0]);
	int m = 0;
	int w[100];
	ConstructionTopDown(v, n, w, m);
	afisare(w, m);
	system("pause");
	return 0;
}