import java.util.Calendar;

public class HeapSort {

	public long heap_sort(int []x){
		Calendar befor=Calendar.getInstance();
		for(int i=x.length/2-1;i>=0;i--){
			mentHeap(x,i);
			}

		Calendar after=Calendar.getInstance();
		return (after.getTimeInMillis()-befor.getTimeInMillis());
	}
	private void mentHeap(int []x,int m){

		int largest;
		int left=(m+1)*2-1;
		int right= left+1;
		largest=m;
		if(left<x.length && x[left]>x[m])
			largest=left;
		if(right<x.length && x[right]>x[largest])
			largest=right;

		if(largest!=m){
			int temp=x[m];
			x[m]=x[largest];
			x[largest]=temp;
			mentHeap(x,largest);
		}
	}

}