import java.util.Arrays;

public class HeapSort {
 
 public static void heapSort(int[] data) {
  heapAdjust(data, 0, data.length - 1);
  for (int i = data.length - 1; i > 0; i--) {
   swap(data, 0, i);
   moveDown(data, 0, i - 1);
  }
 }
 
 /**
  * 自上向下建堆
  * @param data
  * @param start
  * @param end
  */
 private static void heapAdjust(int[] data, int start, int end) {
  int lastBranch = data.length/2 - 1;
  for (int i = lastBranch; i >= 0; i--) {
      moveDown(data, i, data.length - 1);
  }
 }
 
 /**
  * 自上向下調(diào)整堆
  * @param data
  * @param first
  * @param last
  */
 private static void moveDown(int[] data, int first, int last) {
  int larger = 2 * first + 1;
  while (larger <= last) {
      if (larger < last && data[larger] < data[larger + 1]) { //find the larger child
          larger++;
      }
   if (data[first] < data[larger]) { //move down on larger child
       swap(data, first, larger);

    first = larger;
    larger = 2 * first + 1;  
   } else {
       larger = last + 1;    //exit the while loop
   }
  }
 }

 private static void swap(int[] data, int i, int j) {
  // swap
  int temp = data[i]; 
  data[i] = data[j];
  data[j] = temp;
 }
 
 public static void main(String[] args) {
  int[] a = {3, 4, 1, 5, 9, 3, 2, 8, 10};
  heapSort(a);
  System.out.println(Arrays.toString(a));
 }
}