public static void heapSort(int[] array) {
		// build heap (percolate up)
		for(int i=1; i<array.length; i++) {
			int insert = array[i];
			int hole = i+1;
			for(;hole>1&&insert>array[hole/2-1]; hole/=2) {
				array[hole-1] = array[hole/2-1];
			}
			array[hole-1] = insert;
		}
		
		// sort heap (percolate down)
		for(int i=array.length-1; i>0; i--) {
			int tmp = array[i];
			array[i] = array[0];
			array[0] = tmp;
			
			int hole = 1;
			int current = array[hole-1];
			int child;
			for(; hole*2<=i; hole=child) {
				child = hole*2;
				if(child!=i && array[child]>array[child-1]) {
					child++;
				} 
				
				if(current<array[child-1]) {
					array[hole-1] = array[child-1];
				} else {
					break;
				}
			}
			array[hole-1] = current;
		}
		
		System.out.println(Arrays.toString(array));
	}