#include<iostream.h>

#define MAX 10

class heapsort
{
	private : int n, h[MAX];
	public  : int get_n()
		  {
			return n;
		  }
		  void read();
		  void heapify(int);
		  void sort();
		  void display();
};

void heapsort :: read()
{
	int i;
	cout << "\nEnter the number of elements in the array : ";
	cin  >> n;
	cout << "\nEnter the elements of the array\n\n";
	for (i = 1; i <= n; i++)
		cin >> h[i];
}

void heapsort :: heapify(int n)
{
	int i, j, k, v, heap;
	for (i = n / 2; i >= 1; i--)
	{
		k = i;
		v = h[k];
		heap = 0;
		while (!heap && 2 * k <= n)
		{
			j = 2 * k;
			if (j < n)
				if (h[j] < h[j + 1])
					j = j + 1;
			if (v >= h[j])
				heap = 1;
			else
			{
				h[k] = h[j];
				k = j;
			}
		}
		h[k] = v;
	}
}

void heapsort :: sort()
{
	int i, last, temp;
	last = n;
	for (i = 1; i <= n; i++)
	{
		temp = h[last];
		h[last] = h[1];
		h[1] = temp;
		heapify(--last);
	}
}

void heapsort :: display()
{
	int i;
	for (i = 1; i <= n; i++)
		cout << h[i] << endl;
}

int main()
{
	heapsort hs;
	hs.read();
	hs.heapify(hs.get_n());
	cout << "\nThe elements after constructing the heap is\n\n";
	hs.display();
	hs.sort();
	cout << "\nThe elements sorted in ascending order is\n\n";
	hs.display();
	return 0;
}