堆，可以保证max/min是O(1)的时间，通常用来查找最大/最小值。
    本质上是一个完全二叉树，存储结构可以用数组表示。父节点位置为i，则左子节点位置为2i+1，右子节点位置为2i+2。
    (java中的优先队列中用的堆为小顶堆，下面用大顶堆)

    基本操作：

    1.     //返回一个索引所表示的元素的父亲节点索引
    2.     private int parent(int index){
    3.         if(index==0)
    4.             throw new IllegalArgumentException("index- 0 doesn't have parent.");
    5.         return (index-1)/2;
    6.     }
    7.     //返回左孩子节点索引
    8.     private int leftChild(int index){
    9.         return index*2 + 1;
    10.     }
    11.     //返回右孩子节点索引
    12.     private int rightChild(int index){
    13.         return index*2 + 2;
    14.     }

    向堆中添加元素
    向堆中添加元素就是向数组尾中添加元素，然后使其满足堆的性质。
    要满足堆的性质，我们就要定义一个siftUp（上浮）操作，将新加入堆的元素与其父节点做对比，如果新加入元素较大，则调用数组中的swap方法将两个元素交换位置，重复此过程，直到新加入元素小于其父节点元素或者已经上浮到了根节点 

    1. //k为新加入的元素索引，即数组的最后一个元素索引
    2. private void siftUp(int k){
    4.     while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0){
    5.         data.swap(k,parent(k));
    6.         k = parent(k);
    7.     }
    8. }
    10.  public void add(E e){
    11.      data.addLast(e);
    12.      siftUp(data.getSize() - 1);
    13. }

    查看堆中的中最大元素
    就是元素0的值

    1. public E findMax(){
    2.     if(data.getSize()==0){
    3.         throw new IllegalArgumentException("can not findMax when heap is empty");
    4.     }
    5.     return data.get(0);
    6. }

    取出堆中的最大元素
    首先用findMax函数取出并保存堆中最大的元素，然后将数组中的最后一个元素与第一个元素进行交换（swap），然后移除数组中的最后一个元素，然后对根节点的元素进行siftDown（下沉）操作，即不断与两个子节点中较大的节点比较，如果比较大的节点还要小，就与其交换。

    1. private void siftDown(int k){
    2.     //判断当前节点是否有左孩子
    3.     while(leftChild(k) < data.getSize()){
    4.         int j = leftChild(k);
    5.         //判断当前节点是否有右孩子且右孩子比左孩子大
    6.         if(j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j))>0){
    7.             j = rightChild(k);
    8.         }
    9.         //判断当前节点与左右孩子节点中较大那个的大小比较
    10.         if(data.get(k).compareTo(data.get(j)) >= 0){
    11.             break;
    12.         }
    13.         data.swap(k,j);
    14.         k = j;
    15.     }
    16. }
    18. public E extractMax(){
    19.     E ret = findMax();
    20.     data.swap(0,data.getSize() - 1);
    21.     data.removeLast();
    22.     siftDown(0);
    23.     return ret;
    24. }

    heapify
    heapify（数组建堆）是传入一个数组，将数组转化的一个堆的方法，我们首先要在数组中定义一个构造方法，接收一个指定的数组将其储存到自身数组中

    1. public Array(E[] arr){
    2.     data = (E[])new Object[arr.length];
    3.     for(int i = 0 ; i<arr.length ; i ++){
    4.         data[i] = arr[i];
    5.         size = arr.length;
    6.     }
    7. }

    然后从堆中的最后一个不为叶子节点的节点开始，进行siftDown操作，直到根节点结束。这样一来就满足了堆的定义，那么如何找到最后一个不为叶子节点的节点呢？其实很容易，就是数组中最后一个元素的父亲节点索引所在的位置就是最后一个不为叶子节点的节点。即（size-2）/2所在的位置。

    1. public MaxHeap(E[] arr){
    2.     int i = parent(arr.length-1);
    3.     data = new Array<>(arr);
    4.     while(i>=0){
    5.         siftDown(i);
    6.         i--;
    7.     }
    8. }