import java.util.Scanner ;public class MaxPQ<Key extends Comparable<Key>>{	private int N = 0 ;	private Key[] pq ; 		public MaxPQ(int max){		pq = (Key[])new Comparable[max+1] ;	}		public MaxPQ(Key[] a){		pq = (Key[])new Comparable[a.length+1] ;		for (int i=0;i<a.length;i++) {			insert(a[i]) ;		}	}		public void insert(Key v){		N++ ;		pq[N] = v ;		swim(N) ;	}	private void swim(int k){		if(k>1){			if(less(k/2,k)){				exch(k,k/2) ;				swim(k/2) ;			}else{				return ;			}		}else{			return ;		}	}	private boolean less(int i,int j){		return pq[i].compareTo(pq[j])<0 ;	}	private void exch(int i, int j){		Key t = pq[i] ;		pq[i] = pq[j] ;		pq[j] = t ;	}	public Key max(){		return pq[1] ;	}		public Key delMax(){		Key max = pq[1] ;		pq[1] = pq[N] ;		N-- ;		pq[N+1] = null ;		sink(1) ;		return max ;	}	private void sink(int k){		if(2*k<=N){			int t = k ;			if(less(t,2*k)) {				t = 2*k ;			}			if(2*k+1<=N && less(t,2*k+1)){				t = 2*k+1 ;			}			if(t!=k){				exch(t,k) ;				sink(t) ;			}else{				return ;			}		}else{			return ;		}	}		public boolean isEmpty(){		return N == 0 ;	}		public int size(){		return N ;	}	public static void main(String[] args) {		System.out.println("please input the lenghth of heap: ") ;		Scanner sc = new Scanner(System.in) ;		int len = sc.nextInt() ;		MaxPQ<Integer> pq = new MaxPQ<Integer>(len) ;		System.out.println("please input the items:") ;		for(int i=0;i<len;i++){			pq.insert(sc.nextInt()) ;		}		for (int i=0;i<len;i++) {		 	System.out.print(pq.delMax() + " ") ;			} 		} }

import java.util.Scanner ;public class MinPQ<Key extends Comparable<Key>>{	private int N = 0 ;	private Key[] pq ; 		public MinPQ(int max){		pq = (Key[])new Comparable[max+1] ;	}		public MinPQ(Key[] a){		pq = (Key[])new Comparable[a.length+1] ;		for (int i=0;i<a.length;i++) {			insert(a[i]) ;			}	}		public void insert(Key v){		N++ ;		pq[N] = v ;		swim(N) ;	}	private void swim(int k){		if(k>1){			if(less(k,k/2)){				exch(k,k/2) ;				swim(k/2) ;			}else{				return ;			}		}else{			return ;		}	}	private boolean less(int i,int j){		return pq[i].compareTo(pq[j])<0 ;	}	private void exch(int i, int j){		Key t = pq[i] ;		pq[i] = pq[j] ;		pq[j] = t ;	}	public Key min(){		return pq[1] ;	}		public Key delMin(){		Key max = pq[1] ;		pq[1] = pq[N] ;		N-- ;		pq[N+1] = null ;		sink(1) ;		return max ;	}	private void sink(int k){		if(2*k<=N){			int t = k ;			if(less(2*k,t)) {				t = 2*k ;			}			if(2*k+1<=N && less(2*k+1,t)){				t = 2*k+1 ;			}			if(t!=k){				exch(t,k) ;				sink(t) ;			}else{				return ;			}		}else{			return ;		}	}		public boolean isEmpty(){		return N == 0 ;	}		public int size(){		return N ;	}	public static void main(String[] args) {		//System.out.println("please input the lenghth of heap: ") ;		//Scanner sc = new Scanner(System.in) ;		//int len = sc.nextInt() ;		//MinPQ<Integer> pq = new MinPQ<Integer>(len) ;		//System.out.println("please input the items:") ;		//int len = sc.nextInt() ;		//for(int i=0;i<len;i++){		//	pq.insert(sc.nextInt()) ;		//}		Integer[] a = {10,9,8,7,6,5,4,3,2,1} ; 		MinPQ<Integer> pq = new MinPQ<Integer>(a) ;		for (int i=0;i<a.length;i++) {		 	System.out.print(pq.delMin() + " ") ;			} 		} }

import java.util.Scanner ;public class HeapSort{	public static void heapSort(Comparable[] a){		int N = a.length-1 ;		for(int i=N/2;i>=1;i--){     //for循环构造了最大堆；			sink(a,i,N) ;		}		while(N>1){                  //while循环完成了从小到大排序			exch(a,1,N) ;			N-- ;			sink(a,1,N) ;		}	}	private static void sink(Comparable[] a, int i, int j){		if(2*i<=j){			int t = i ;			if(less(a[t],a[2*i])){				t = 2*i ;			}			if(2*i+1<=j && less(a[t],a[2*i+1])){				t = 2*i+1 ;			}			if(t!=i){				exch(a,t,i) ;				sink(a,t,j) ;			}else{				return ;			}		}else{			return ;		}	}	private static boolean less(Comparable v, Comparable w){		return v.compareTo(w)<0 ;	}	private static void exch(Comparable[] a, int i, int j){		Comparable temp = a[i] ;		a[i] = a[j] ;		a[j] = temp ;	}	private static void show(Comparable[] a){		for(int i=0;i<a.length;i++){			System.out.print(a[i] + " ") ;		}		System.out.println() ;	}	public static boolean isSorted(Comparable[] a){		for(int i=2;i<a.length;i++){			if(less(a[i],a[i-1])){				return false ;			}		}		return true ;	}	public static void main(String[] args){				System.out.println("please input the length of array:") ;				Scanner sc = new Scanner(System.in) ;		int len = sc.nextInt() ;		Integer[] a = new Integer[len] ;		System.out.println("please input the numbers of array:") ;		for (int i=0;i<len;i++) {			a[i] = sc.nextInt() ;		}				if (!isSorted(a)) {			heapSort(a) ;		}		show(a) ;	} }