public class MaxHeap<T extends Comparable<? super T>> {
 private T[] data;
 private int size;
 private int capacity;
 
 public MaxHeap(int capacity) {
  this.data = (T[]) new Comparable[capacity + 1];
  size = 0;
  this.capacity = capacity;
 }
 
 public int size() {
  return this.size;
 }
 
 public boolean isEmpty() {
  return size == 0;
 }
 
 public int getCapacity() {
  return this.capacity;
 }
 
 /**
  * @return 查看最大根(只看不刪, 與popMax對(duì)比)
  */
 public T seekMax() {
  return data[1];
 }
 
 public void swap(int i, int j) {
  if (i != j) {
   T temp = data[i];
   data[i] = data[j];
   data[j] = temp;
  }
 }
 
 public void insert(T item) {
  size++;
  data[size] = item;
  shiftUp(size);
 }
 
 /**
  * @return 彈出最大根(彈出意味著刪除, 與seekMax對(duì)比)
  */
 public T popMax() {
  swap(1, size--);
  shiftDown(1);
  return data[size + 1];
 }
 
 /**
  * @param child 孩子節(jié)點(diǎn)下角標(biāo)是child，父節(jié)點(diǎn)下角表是child/2
  */
 public void shiftUp(int child) {
  while (child > 1 && data[child].compareTo(data[child / 2]) > 0) {
   swap(child, child / 2);
   child = child / 2;
  }
 }
 
 /**
  * @param a data數(shù)組中某個(gè)元素的下角標(biāo)
  * @param b data數(shù)組中某個(gè)元素的下角標(biāo)
  * @return 哪個(gè)元素大就返回哪個(gè)的下角標(biāo)
  */
 private int max(int a, int b) {
  if (data[a].compareTo(data[b]) < 0) {//如果data[b]大
   return b;//返回b
  } else {//如果data[a]大
   return a;//返回a
  }
 }
 
 /**
  * @param a data數(shù)組中某個(gè)元素的下角標(biāo)
  * @param b data數(shù)組中某個(gè)元素的下角標(biāo)
  * @param c data數(shù)組中某個(gè)元素的下角標(biāo)
  * @return 哪個(gè)元素大就返回哪個(gè)的下角標(biāo)
  */
 private int max(int a, int b, int c) {
  int biggest = max(a, b);
  biggest = max(biggest, c);
  return biggest;
 }
 
 
 /**
  * @param father 父節(jié)點(diǎn)下角標(biāo)是father,左右兩個(gè)孩子節(jié)點(diǎn)的下角表分別是：father*2 和 father*2+1
  */
 public void shiftDown(int father) {
  while (true) {
   int lchild = father * 2;//左孩子
   int rchild = father * 2 + 1;//右孩子
   int newFather = father;//newFather即將更新，父、左、右三個(gè)結(jié)點(diǎn)誰大，newFather就是誰的下角標(biāo)
 
   if (lchild > size) {//如果該father結(jié)點(diǎn)既沒有左孩子，也沒有右孩子
    return;
   } else if (rchild > size) {//如果該father結(jié)點(diǎn)只有左孩子，沒有右孩子
    newFather = max(father, lchild);
   } else {//如果該father結(jié)點(diǎn)既有左孩子，又有右孩子
    newFather = max(father, lchild, rchild);
   }
 
   if (newFather == father) {//說明father比兩個(gè)子結(jié)點(diǎn)都要大，表名已經(jīng)是大根堆，不用繼續(xù)調(diào)整了
    return;
   } else {//否則，還需要繼續(xù)調(diào)整堆，直到滿足大根堆條件為止
    swap(father, newFather);//值進(jìn)行交換
    father = newFather;//更新father的值，相當(dāng)于繼續(xù)調(diào)整shiftDown(newFather)
   }
  }
 }
 
 public static <T extends Comparable<? super T>> void sort(T[] arr) {
  int len = arr.length;
  //入堆
  MaxHeap<T> maxHeap = new MaxHeap<T>(len);
  for (int i = 0; i < len; i++) {
   maxHeap.insert(arr[i]);
  }
  //出堆
  for (int i = len - 1; i >= 0; i--) {
   arr[i] = maxHeap.popMax();
  }
 }
 
 public static void printArr(Object[] arr) {
  for (Object o : arr) {
   System.out.print(o);
   System.out.print("\t");
  }
  System.out.println();
 }
 
 public static void main(String args[]) {
  Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
  printArr(arr);//3 5 1 7 2 9 8 0 4 6
  sort(arr);
  printArr(arr);//0 1 2 3 4 5 6 7 8 9
 }
}

public class MaxHeap<T extends Comparable<? super T>> {
 private T[] data;
 private int size;
 private int capacity;
 
 public MaxHeap(int capacity) {
  this.capacity = capacity;
  this.size = 0;
  this.data = (T[]) new Comparable[capacity + 1];
 }
 
 public MaxHeap(T[] arr) {//heapify,數(shù)組建堆
  capacity = arr.length;
  data = (T[]) new Comparable[capacity + 1];
  System.arraycopy(arr, 0, data, 1, arr.length);
  size = arr.length;
  for (int i = size / 2; i >= 1; i--) {
   shiftDown(i);
  }
 }
 
 public int size() {
  return this.size;
 }
 
 public int getCapacity() {
  return this.capacity;
 }
 
 public boolean isEmpty() {
  return size == 0;
 }
 
 public T seekMax() {
  return data[1];
 }
 
 public void swap(int i, int j) {
  if (i != j) {
   T temp = data[i];
   data[i] = data[j];
   data[j] = temp;
  }
 }
 
 public void insert(T item) {
  size++;
  data[size] = item;
  shiftUp(size);
 }
 
 public T popMax() {
  swap(1, size--);
  shiftDown(1);
  return data[size + 1];
 }
 
 public void shiftUp(int child) {
  while (child > 1 && data[child].compareTo(data[child / 2]) > 0) {
   swap(child, child / 2);
   child /= 2;
  }
 }
 
 /**
  * @param a data數(shù)組中某個(gè)元素的下角標(biāo)
  * @param b data數(shù)組中某個(gè)元素的下角標(biāo)
  * @return 哪個(gè)元素大就返回哪個(gè)的下角標(biāo)
  */
 private int max(int a, int b) {
  if (data[a].compareTo(data[b]) < 0) {//如果data[b]大
   return b;//返回b
  } else {//如果data[a]大
   return a;//返回a
  }
 }
 
 /**
  * @param a data數(shù)組中某個(gè)元素的下角標(biāo)
  * @param b data數(shù)組中某個(gè)元素的下角標(biāo)
  * @param c data數(shù)組中某個(gè)元素的下角標(biāo)
  * @return 哪個(gè)元素大就返回哪個(gè)的下角標(biāo)
  */
 private int max(int a, int b, int c) {
  int biggest = max(a, b);
  biggest = max(biggest, c);
  return biggest;
 }
 
 public void shiftDown(int father) {
  while (true) {
   int lchild = father * 2;
   int rchild = father * 2 + 1;
   int newFather = father;//這里賦不賦值無所謂，如果把下面這個(gè)return改成break,那就必須賦值了
 
   if (lchild > size) {//如果沒有左、右孩子
    return;
   } else if (rchild > size) {//如果沒有右孩子
    newFather = max(father, lchild);
   } else {//如果有左、右孩子
    newFather = max(father, lchild, rchild);
   }
 
   if (newFather == father) {//如果原父結(jié)點(diǎn)就是三者最大，則不用繼續(xù)整理堆了
    return;
   } else {//父節(jié)點(diǎn)不是最大，則把大的孩子交換上來，然后繼續(xù)往下堆調(diào)整，直到滿足大根堆為止
    swap(newFather, father);
    father = newFather;//相當(dāng)于繼續(xù)shiftDown(newFather)。假如newFather原來是father的左孩子，那就相當(dāng)于shiftDown(2*father)
   }
  }
 }
 
 public static <T extends Comparable<? super T>> void sort(T[] arr) {
  int len = arr.length;
  MaxHeap<T> maxHeap = new MaxHeap<>(arr);
  for (int i = len - 1; i >= 0; i--) {
   arr[i] = maxHeap.popMax();
  }
 }
 
 public static void printArr(Object[] arr) {
  for (Object o : arr) {
   System.out.print(o);
   System.out.print("\t");
  }
  System.out.println();
 }
 
 public static void main(String args[]) {
  Integer[] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6};
  printArr(arr);//3 5 1 7 2 9 8 0 4 6
  sort(arr);
  printArr(arr);//0 1 2 3 4 5 6 7 8 9
 }
}