数据结构——堆和堆的应用

一、什么是堆？

堆是一种特殊的树，堆要满足下面两点。
1、堆是一个完全二叉树；
2、堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
通过下图可以更好理解：

二、怎么实现一个堆？

要实现一个堆最重要的一个操作就是堆化，堆化有两种方法。（下面的案例我们用小顶堆来演示）

这里有个小提示: 我们用数组来实现堆时，一般都假设堆中的数据是从数组下标为1的位置开始存储，如果节点的下标是i，那左子节点的下标就是2 * i,右子节点的下标就是2 * i + 1，父节点的下标就是 i/2；（如果从0开始的话，下标会多一次运算。）

1、从下往上的堆化
让新插入的节点与父节点对比大小。如果不满足子节点大于等于父节点，就互换两个节点。一直重复这个过程，直到父子节点之间满足堆的第二个要求。
我们用代码实现如下：

public class ArrayHeap(
  // 数组，从下标1开始存储数据  
  private int[] root; 
  // 堆的大小
  private int size;
  // 堆已经存储了多少个数据
  private int count;

  public ArrayHeap(int capacity){
    root = new int[capacity +1];
    size = capacity;
    count = 0;
  }

  /**
   * 插入数据
   * 
   * @param data 要插入的数据
   * @return 返回是否成功
  */
   public boolean insert(int data){
    // 堆满了
    if(count >= size) return false;
    root[++count] = data;
    // 堆化
    heapify(root, count);
    reutrn true;
  }
  /**
   * 自下而上堆化
   *
   * @param arr 数组
   * @param i 节点下标
  */
  public void heapify(int[] arr, int i){
    while( i/2 > 0 && a[i] < arr[i/2]){ // 当节点小于父节点时
        // 交换
        swap(arr, i, i/2);
        // 继续判断
        i = i/2;
    }
  }

// 交换两个位置的值
 private void swap(int[] arr, int u, int v){
    int temp = arr[u];
    arr[u] = arr[v];
    arr[v] = temp;
 }
}

2、从上往下的堆化
我们把最后一个节点放到堆顶，然后利用同样的父子节点对比方法，对于不满足父子节点大小关系的，互换两个节点，并且重复进行这个过程，直到父子节点之间满足大小关系为止。
这里我们实现移除堆顶节点，代码如下：

/**
 * 删除堆顶元素
*/
public int removeMin(){
  // 堆中没有数据
  if(count == 0) return -1;
  int data = root[1];
  // 把最后一个节点放到堆顶
  root[1] = root[count]
  // 堆化
  heapifyMin(root, count, 1);
  return data;
}

/**
  * 自上而下的堆化操作
  *
  *@param arr 数组
  *@param n 堆中元素个数
  *@param i 当前节点
*/
public void heapifyMin(int[] arr, int n, int i){
  while(true){
    // 找出要与节点 i 交换的子节点 
    int minPos = i;
    if(i*2 <= n && arr[i*2] < arr[minPos]){
      minPos = i * 2;
    }
    if(i*2 + 1 <= n && arr[i*2 + 1] < arr[minPos]){
      minPos = i * 2 + 1;
    }
    // 如果没有要交换的，说明子节点都大于节点i
    if(i == minPos){
      return;
    }
    // 互换位置
    swap(arr, i, minPos);
    i = minPos;
 }
}

3、建堆和排序
不借助另一个数组，就在原数组上操作。有两种思路。

第一种，把元素一个个往堆中插入，利用上面的插入操作，就可以组成堆。

第二种，从后往前处理数组，并且每个数据都是从上往下堆化，跟上面删除堆顶的堆化操作一样。

第二种实现代码如下：

 public void buildHeap(int[] arr, int n){
     for(int i = n/2; i >= 1; i--){
       // 调用上面删除堆顶的堆化操作
       heapifyMin(arr, n, i);
    } 
 }

建堆的实际时间复杂度是O(n), 按道理来说每个节点堆化的时间复杂度是O(logn)，叶子节点是不需要堆化的，所以需要堆化的节点是n/2 + 1个节点，那是不是堆化的总时间复杂度就是O(nlog)呢。我们来推导一下。

总的时间复杂度 = 每层的时间复杂度之和
f(n) = 1h + 2¹ * (h-1) + 2² * (h-2)+ 2³ * (h-3) + ... + 2^h-1 * 1
把两边都乘2
2 * f(n) = 2¹h + 2² * (h-1) + 2³ * (h-2) + 2⁴ * (h-3) + ... + 2^h * 1
两个相减
f(n) = -h + 2 + 2² + 2 + 2³ + ...+ 2^k + ... + 2^h-1 +2^h = 2^h+1 - h -2

因为 h = log₂n 代入公式f(n)，就能得到 f(n) = O(n),所以，建堆的时间复杂度就是O(n)。

现在我们把建好堆的数组进行排序，这个过程有点类似上面删除堆顶元素，当堆顶的元素移除之后，把下标为n的元素放到堆顶，将移除的元素放到下标n的位置，将剩下n-1个元素重新构建成堆。一直重复到下标为1的一个元素，排序工作就完成了。代码如下：

/**
 * 排序
 * @param arr 数组
 * @param n 数据的个数，数组arr中的数据从下标1到n的位置。
*/
public static void sort(int[] arr, int n){
  buildHeap(arr, n);
  for(int i = n; i > 1; i--){
    // 交换位置
    swap(arr, 1, i);
    // 重新堆化
    headify(arr, i, 1);
  }
}

三、堆的应用

1、优先级队列
我们知道队列最大的特性就是先进先出。但在优先级队列，是按照优先级来，优先级最高的，最先出队。

一个堆就可以看作一个优先级队列 。在优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素（这里的堆是大顶堆）；常见案例有 合并有充小文件、高性能定时器

2、利用堆求 Top K
如何在一个包含n个数据的数组中，查找前K大数据呢？先维护一个大小为K的小顶堆，顺序遍历数组，从数组中取出数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。等遍历完之后，堆中数据就是前K大元素。

2、利用堆求中位数
借助堆这种数据结构，我们不用排序，就可以非常高效地实现求中位数的操作。具体实现代码如下：

    /**
     * 用堆求数组的中位数；维护两个堆，大顶堆中存储前半部分数据，
     * 小顶堆中存储后半部分数据。且小顶堆中的数据都大于大顶堆中的数据
     *
     * @param arr 数组
     * @param n   数据个数
     * @return 中位数
     */
    public int getMedian(int[] arr, int n) {
        // 计算两个顶堆的大小
        int minSize = n / 2;
        int maxSize = n / 2;
        // 如果数组大小是奇数，大顶堆存储 n/2+1个数据
        // 这样就不管数组大小是奇偶，中位值都是大顶堆的第一个值
        if (n % 2 == 1) {
            maxSize = n / 2 + 1;
        }
         // 大顶堆 
        ArrayHeap heapMax = new ArrayHeap(maxSize);
        // 小顶堆 
        ArrayHeap heapMin = new ArrayHeap(minSize);
        // 往两个堆中添加数据,利用小顶堆的特性把数组前minSize大的值放入heapMin中
        for (int i = 0; i < n; i++) {
            // 如果heapMin满了
            if (heapMin.isFull()) {
                int temp = arr[i];
                // 如果当前值大于heapMin第一个值，说明heapMin中的值还不是数组中最大的值
                if (arr[i] > heapMin.root[1]) {
                    // 把heapMin第一个值替换成当前值
                    temp = heapMin.root[1];
                    heapMin.root[1] = arr[i];
                    // 重新堆化heapMin
                    heapMin.heapipyMin(heapMin.root, minSize, 1);
                }
                // 把小顶堆踢出来的值或者小于小顶堆第一个值添加到hemapMax中
                heapMax.insertMax(temp);
            } else {
                // 把数据插入heapMin
                heapMin.insertMin(arr[i]);
            }
        }
        return heapMax.root[1];
    }