void heapify(int A[],int i,int last){
int le,ri,temp,largest;

	le= 2*i+1;
	ri= 2*i+2;
	if (le<=last && A[le] >A[i])
		largest = le;
	else
		largest = i;

	if ( ri <=last  && A[ri] > A[largest])
		largest = ri;

	if (largest != i)
		{
		temp= A[i];
		A[i]=A[largest];
		A[largest]=temp;

		heapify(A,largest,last);
		}

}

void buildheap(int A[],int last){
int heapsize,j;

heapsize=(last-1)/2;
for (j=heapsize;j>=0;j--)
	heapify(A,j,last);
}

void heapsort(int A[],int last)
{
	int temp,i;
	buildheap(A,last);
	temp = A[0];
	A[0]=A[last-1];
	A[last-1]= temp;

	for(i=1;i<last;i++)
	{
		heapify(A,0,last-i-1);
		temp =A[0];
		A[0]=A[last-i-1];
		A[last-i-1]= temp;
	}
}