1.堆的定义：

堆是一种特别的二叉树，完全二叉树。
完全二叉树；
每一个节点的值都必须 大于等于或者小于等于 其孩子节点的值。
2.1>如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；
2.2>如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空，且则该节点之后的队列中的结点都为叶子节点，该树才是完全二叉树，否则就不是完全二叉树；
堆适用于动态元素添加，使用动态数组实现堆。
用链表很难实现堆，因为siftUp无法通过链表实现。

2.最大堆与最小堆：

  • 最大堆：root 节点最大

  • 最小堆：root 节点最小 ```java public class MaxHeap >{ private Array data; public MaxHeap(int capacity){

    1.   data = new Array<>(capacity);

    } public MaxHeap(){

      data = new Array<>();

    }

    // 将传入的数组进行堆化 public MaxHeap(E[] arr){

      data = new Array<>(arr);
   if(arr.length != 1){
      // 把每层节点遍历，然后进行下移操作，最后形成堆
      for(int j = parent(data.size() - 1); j >=0; j--){
          siftDown(j);
      }
  }

    }

    // 获取左子节点 public int leftChild(int k){

      return 2*k+1;

    }

    // 获取右子节点 public int leftChild(int k){

      return 2*k+2;

    }

    // 获取父节点 public int parent(int k){

      // root 节点无父亲节点
  if (index == 0) {
      throw new IllegalArgumentException("Node has no parent Node");
  }
  return (k - 1) / 2;

    }

    //添加元素 public void add(E value){

      data.addLast(value);
  // 将尾部元素上移，直到到一个正确位置
  siftUp(data.getSize() - 1);

    }

    // 元素上浮 public void siftUp(int k){

      while(k > 0 && data[k] > data[parent[k]]){
      data.swap(k, parent[k]);
      k = parent[k];
  }

    }

    //获取最大值 public E findMax(){

      if(data.length() == 0){
      throw new exception("Heap is empty");
  }
  return data.get(0);

    }

    // 删除元素,每次删除顶部元素(即最大值) public E remove(){

      E res = findMax();
  data[0] = data[arr.length - 1];
  data.removeLast();
  swiftDown(0);
  return res;

    }

    // 将元素下沉 public void swiftDown(int k){

      // 看 k 是否为叶子节点
  // 记录 j 为要交换的位置
  if(leftchild(k) < data.getSize()){
      int j = leftchild(k);
      if(rightchild(k) <= data.size() - 1 && arr[rightchild[k]] > arr[leftchild[k]]){
          j = rightchild(k);
      }
      if(arr[k].compareTo(arr[j]) >= 0){
          break;
      }
      swap(j, k);
      k = j;
  }

    }

// 替换最大元素
public E replace(E e) {
    // 取出最大元素
    E res = findMax();
    // 将最大元素替换为e, 设置
    data.set(0, e);
    // 然后进行 SiftDown
    siftDown(0);
    return res;
}

}

<a name="AaC41"></a>
## 3.堆排序：（是利用堆root 节点最大进行排序，而不是把数组仅仅堆化）
```java
// 原地排序 ： 不断获取最大元素与最小元素，使之在 top 和 data.length - 1 位置， 然后互换
// 最大元素放在最后，之后进行交换
// 优化了空间复杂度
public static <E extends Comparable<E>> sort(E[] arr){
    // 对于 arr 每层节点均为下沉操作
    if(arr.lengt == 1) return
    // 遍历整个数组, 将整个数组堆化
    // 将数组进行 siftDown 操作
       for(int i = (arr.length - 2) / 2; i >=0; i--){
        // 参数 ： 数组 ， 节点， 数组大小
        siftDown(arr, i, arr.length);
    }
    // 此时由于堆的性质，数组的第一个元素为最大元素
    // 整个数组从小到大的顺序排列
    // 此时将元素与最后一个元素进行交换，再进行siftDown操作,直到数组遍历完成
    for(int i = data.length() - 1; i >= 0; i++ ){
        swap(arr, 0, i);
        // siftDown中的 i 表示数组长度， 在实现堆的时候用了 i ,是为了判断是否为叶子节点
        // [0, i -1] 进行 siftDown 操作
        siftDown(arr, 0, i);
    }
}

// i 需要进行下沉操作的节点
public void siftDown(E[] arr, int i, int n){
    // 确认不是叶子节点
    if( (2 * i + 1) < n ){
        int j = (2 * i + 1);
        if( j + 1 < n && arr[j + 1] > arr[j]){
            j++;
        }
        if(arr[i] > arr[j]){
            break;
        }
        swap(i, j);
        i = j;
    }

}

堆的作用：（优先队列）

image.png