#include<iostream>
using namespace std;
void heapsort(int [],int);
void heapify(int [],int);
void adjust(int [],int);

int main()
{
	int v[50],n,i;

	cout<<"Introdu numarul de elemente ce urmeaza sa fie sortate ";
	cin>>n;
	
	cout<<endl;
	cout<<"\nIntrodu elemente ";
	for (i=0;i<n;i++)
	cin>>v[i];

	cout<<"\nInainte de sortare: ";
	for (i=0;i<n;i++)
	cout<<v[i]<<" ";
	cout<<endl;
	
	heapsort(v,n);

	cout<<"\nDupa sortare: ";
	for (i=0;i<n;i++)
	cout<<v[i]<<" ";
	cout<<endl;

}

void heapsort (int v[],int n)
{
	int i,t;
	heapify(v,n);
	
	for (i=n-1;i>0;i--)
	{
		t=v[0];
		v[0]=v[i];
		v[i]=t;
		adjust(v,i);
	}
}

void heapify (int v[],int n)
{
	int item,i,j,k;
	
	for (k=1;k<n;k++)	
	{
	item=v[k];
	i=k;
	j=(i-1)/2;

	while ( (i>0) && (item>v[j]) )
	{
	v[i]=v[j];
	i=j;
	j=(i-1)/2;
	}
	v[i]=item;
	}
}

void adjust (int v[],int n)
{
	int item,i,j;
	
	j=0;
	item=v[j];
	i=2*j+1;

	while (i<=n-1)
	{
	if (i+1<=n-1)
		if (v[i]<v[i+1])
		i++;
	if (item<v[i])
	{
	v[j]=v[i];
	j=i;
	i=2*j+1;
	}
	else
		break;
	}
	v[j]=item;
}