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对比)
   */
 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对比)
   */
 public T popMax() {
  swap(1, size--);
  shiftDown(1);
  return data[size + 1];
 }
 /**
   * @param child 孩子节点下角标是child，父节点下角表是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数组中某个元素的下角标
   * @param b data数组中某个元素的下角标
   * @return 哪个元素大就返回哪个的下角标
   */
 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数组中某个元素的下角标
   * @param b data数组中某个元素的下角标
   * @param c data数组中某个元素的下角标
   * @return 哪个元素大就返回哪个的下角标
   */
 private int max(int a, int b, int c) {
  int biggest = max(a, b);
  biggest = max(biggest, c);
  return biggest;
 }
 /**
   * @param father 父节点下角标是father,左右两个孩子节点的下角表分别是：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即将更新，父、左、右三个结点谁大，newFather就是谁的下角标
   if (lchild > size) {
    //如果该father结点既没有左孩子，也没有右孩子
    return;
   } else if (rchild > size) {
    //如果该father结点只有左孩子，没有右孩子
    newFather = max(father, lchild);
   } else {
    //如果该father结点既有左孩子，又有右孩子
    newFather = max(father, lchild, rchild);
   }
   if (newFather == father) {
    //说明father比两个子结点都要大，表名已经是大根堆，不用继续调整了
    return;
   } else {
    //否则，还需要继续调整堆，直到满足大根堆条件为止
    swap(father, newFather);
    //值进行交换
    father = newFather;
    //更新father的值，相当于继续调整shiftDown(newFather)
   }
  }
 }
 public static void main(String[] args) {
  //创建大根堆
  MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
  //向堆里存
  for (int i = 0; i < 100; i++) {
   maxHeap.insert((int) (Math.random() * 100));
  }
  //创建数组
  Integer[] arr = new Integer[100];
  //从堆里取，放进数组里
  for (int i = 0; i < 100; i++) {
   arr[i] = maxHeap.popMax();
   System.out.print(arr[i] + " ");
  }
  System.out.println();
 }
}

public class MaxHeap<T extends Comparable<? super T>> {
 private T[] data;
 private int size;
 private int capacity;
 public MaxHeap(int capacity) {
  data = (T[]) new Comparable[capacity + 1];
  this.capacity = capacity;
  size = 0;
 }
 public int size() {
  return size;
 }
 public Boolean isEmpty() {
  return size == 0;
 }
 public void insert(T item) {
  data[size + 1] = item;
  size++;
  shiftUp(size);
 }
 /**
   * @return 弹出最大根(弹出意味着删除, 与seekMax对比)
   */
 public T popMax() {
  T ret = data[1];
  swap(1, size);
  size--;
  shiftDown(1);
  return ret;
 }
 /**
   * @return 查看最大根(只看不删, 与popMax对比)
   */
 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 shiftUp(int k) {
  while (k > 1 && data[k / 2].compareTo(data[k]) < 0) {
   swap(k, k / 2);
   k /= 2;
  }
 }
 public void shiftDown(int father) {
  while (2 * father <= size) {
   int newFather = 2 * father;
   if (newFather + 1 <= size && data[newFather + 1].compareTo(data[newFather]) > 0) {
    //data[j] data[j+1]两者取大的那个
    newFather = newFather + 1;
   }
   if (data[father].compareTo(data[newFather]) >= 0) {
    break;
   } else {
    swap(father, newFather);
    //值进行交换
    father = newFather;
    //newFather是(2*father)或者是(2*father+1),也就是继续shiftDown(newFather);
   }
  }
 }
 public static void main(String[] args) {
  //创建大根堆
  MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
  //向堆里存
  for (int i = 0; i < 100; i++) {
   maxHeap.insert((int) (Math.random() * 100));
  }
  //创建数组
  Integer[] arr = new Integer[100];
  //从堆里取，放进数组里
  for (int i = 0; i < 100; i++) {
   arr[i] = maxHeap.popMax();
   System.out.print(arr[i] + " ");
  }
  System.out.println();
 }
}