【Java -- 数据结构】什么是堆(Heap)？

前言

这里所说的堆是数据结构中的堆，而不是内存模型中的堆。堆通常是一个可以被看做一棵树，它满足下列性质:

• 堆中任意节点的值总是不大于(不小于)其子节点的值；
• 堆是完全二叉树
• 常常用数组实现

二叉堆是完全二元树或者是近似完全二元树，它分为两种：最大堆和最小堆。 最大堆：父结点的键值总是大于或等于任何一个子节点的键值；最小堆：父结点的键值总是小于或等于任何一个子节点的键值。

优点:

• 插入、删除快，对最大数据项存取快

缺点:

• 对其他数据项存取慢

定义

堆是一种特殊的数，应用场景很多，最经典的就是堆排序，堆排序是一种原地排序，时间复杂度是O(nlogn)、

堆的存储

完全二叉树适合用数组来存储，因为我们不需要存储左右子节点的指针，所以用数组存储完全二叉树比较节省空间。通过下标就能找到其左右子节点和父节点

比如下标为i的节点的左子节点就是下标为i2的节点，右子节点就是下标为i2+1的节点，父节点就是下标为i/2的节点

堆的操作

1. 插入 插入一个元素都，很可能就不满足堆的特性了，我们需要调整让其重新满足特性，这个过程叫做“堆化”

堆化可以分为从上往下和从下往上两种堆化的方法。也就是顺着节点所在的路径往上或者往下比较然后交换。

public class Heap {
  private int[] a; // 数组，从下标 1 开始存储数据
  private int n;  // 堆可以存储的最大数据个数
  private int count; // 堆中已经存储的数据个数

  public Heap(int capacity) {
    a = new int[capacity + 1];
    n = capacity;
    count = 0;
  }

  public void insert(int data) {
    if (count >= n) return; // 堆满了
    ++count;
    a[count] = data;
    int i = count;
    while (i/2 > 0 && a[i] > a[i/2]) { // 自下往上堆化
      swap(a, i, i/2); // swap() 函数作用：交换下标为 i 和 i/2 的两个元素
      i = i/2;
    }
  }
 }

2. 删除堆顶元素 通过堆的第二条特征我们知道，堆顶的元素就是最大或者最小的元素，当我们删除堆顶的元素之后，这个节点就变成了一个空节点，然后让它跟第二大元素位置互换，以此类推，知道这个空节点到成为了叶子节点

上面的方法会出现一个问题，最后叶子节点可能出现在右边，完全二叉树的定义，也就不是一个堆了。

解决这个问题很简单，元素删除后，先把最后一个节点放在栈顶，然后这个节点跟其子节点对比交换，重复此过程直到父子节点满足关系为止。

public void removeMax() {
  if (count == 0) return -1; // 堆中没有数据
  a[1] = a[count];
  --count;
  heapify(a, count, 1);
}

private void heapify(int[] a, int n, int i) { // 自上往下堆化
  while (true) {
    int maxPos = i;
    if (i*2