public class HeapSort{
	int a[];
	public HeapSort(int a[]){
		this.a =a;
	}
	
	public void swap(int i, int j){
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
	
	public void heapify(int j, int n){
		int temp=0;
		while(j<=n){
			if (a[j/2]>a[j]){
				if ((j+1)<=n){
					if (a[j]>a[j+1]){
						swap(j+1,j/2);
						j=j+1;
					}
					else
						swap(j,j/2);
				}
				else
					swap(j,j/2);
			}
			else{
				if ((j+1)<=n){
					if (a[j/2]>a[j+1]){
						swap(j+1, j/2);
						j=j+1;
					}
				}
			}
			j=2*j;
		}
	}
	
	public int[] buildTree(){
		int n=a.length-1;
		int temp;
		for(int i=n;i>0;i--){
			if(a[i/2]>a[i])
				swap(i, i/2);
			heapify(2*i,n);
		}
		return a;
	}
	
	public int[] sort(){
		int temp;
		for (int i=a.length -1; i>1;i--){
			swap(1,i);
			heapify(2,i-1);
		}
		return a;
	}
	
	public static void main(String args[]){
		int a[]={0,16,6,2,6,3,8,4,6,7,4,56,7,42,2}; //there is no use of 1st element of array, i.e. I considered element for index 1 not 0, this make the program look easy and good.
		
		HeapSort hs = new HeapSort(a);
		a = hs.buildTree();
		a = hs.sort();
		
		for(int l=a.length-1;l>0;l--)
			System.out.print(a[l]+" ");
	}
}