[原]数据结构之堆

此文是数据结构与算法之美的学习笔记

堆的概念

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

堆的特点

• 堆是一个完全二叉树（除了最后一层，其他层的节点的个数都是满的，最后一层的节点都是靠左排列）
• 堆中的每个节点的值都必须大于等于或者小于等于其子树中的每个节点的值

每个节点的值都大于等于子树中每个节点的值的堆叫做“ 大顶堆 ”，每个节点的值都小于等于子树中每个节点的值的堆叫做“ 小顶堆 ”

堆的存储

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

比如下标为i的节点的左子节点就是下标为i 2的节点，右子节点就是下标为i 2+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 <= n && a[i] < a[i*2]) maxPos = i*2;
    if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
    if (maxPos == i) break;
    swap(a, i, maxPos);
    i = maxPos;
  }
}

堆排序可以分成两个步骤

1.建堆

第一种：假设堆中只有一个数据，下标为1，然后根据上面堆的插入的逻辑，从下标2到n依次插入就完成了

第二种：因为叶子节点往下堆化只能跟自己比较，所以从第一个非叶子节点开始依次堆化。

private static void buildHeap(int[] a, int n) {
  for (int i = n/2; i >= 1; --i) {
    heapify(a, n, i);
  }
}

private static void heapify(int[] a, int n, int i) {
  while (true) {
    int maxPos = i;
    if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;
    if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;
    if (maxPos == i) break;
    swap(a, i, maxPos);
    i = maxPos;
  }
}

从下标为n/2开始到1的数据进行堆化。下标从n/2+1到n的节点都是叶子节点。

完全二叉树从n/2到n的节点都是叶子节点。

2.排序

堆建完之后，数组中的数据就是按照堆的特性来组织了，数组中的第一个元素就是堆顶的元素，也就是最大或者最小的元素。

如果是大顶堆，总共n个元素。我们把堆顶的元素放到数组的最后一个位置也就是n的位置，然后把最后一个位置放到堆顶，然后剩下的n-1个元素执行堆化的方法。堆化完成之后子在取堆顶元素放在n-1的位置，以此类推直到最后堆中只剩下1个元素为止。

// n 表示数据的个数，数组 a 中的数据从下标 1 到 n 的位置。
public static void sort(int[] a, int n) {
  buildHeap(a, n);
  int k = n;
  while (k > 1) {
    swap(a, 1, k);
    --k;
    heapify(a, k, 1);
  }
}

堆的应用

优先级队列

队列的最大特点是先进先出，在优先级队列中，数据的出队顺序不是先进先出，而是根据优先级来，优先级高的先出队。

堆很适合用来实现优先级队列，堆和优先级队列很像。如果每次都在堆顶取元素的话，那就是一个优先级队列。而往堆中插入一个元素，相当于往优先级队列中插入一个元素。

Java中的优先级队列PriorityQueue，C++中的是priority_queue

优先级队列的应用：

1.合并有序的小文件

假设有100个文件，每个文件100M，里面都存储的有序的字符串，如何把这100个小文件合并成一个大的有序的文件呢？

首先从每个小文件中取出一个字符串，放到一个小顶堆中，堆顶就是最小的元素，取出堆顶的元素放入到大文件的第一位，并把它从堆中删除。然后在从删除的字符串所在的小文件中取出下一个字符串插入到堆中，插入完成后在按照上面的操作取出堆顶元素，在删除在插入，循环这个过程，直到排序完成。

2.高性能定时器

假设有一个定时器，里面维护了很多定时任务，每个任务都设定了一个要触发执行的时间点。定时器每过一段很小的时间就扫描一遍任务，看看有没有需要执行的，如果有就执行。

这种做法很低效：第一如果还有很久才能执行下一个任务，之前的扫描都是无效的。第二每次都扫描又有的表，如果任务表很大的话，非常耗时

这时候就可以使用优先级队列了，按照任务设定的执行时间，存储在优先级队列中，队列的首位就是最先执行的任务。

我们只需拿到队列首位的任务的执行时间点与当前的时间相减，得到时间间隔T，过了时间T之后去取出队列首位的任务执行就好了。这样再也不用遍历任务表了，性能可就提高了。

利用堆求Top K的值

1.静态数据（数据不会变），可以维护一个大小为K的小顶堆，顺序遍历数组，从数组中取出数据与堆顶的元素比较，如果大于堆顶的元素，删除堆顶的元素，然后把这个元素插入到堆中，如果比堆顶的元素小，则不做处理继续遍历数组。直到数组遍历完之后堆中就是前K大的数据了。

2.动态数据（数据会不断加入），维护一个大小为K的小顶堆，每次有插入新元素加入，跟堆顶的元素比较，如果大于堆顶元素，就删除堆顶元素，把新的元素插入堆中，如果小于堆顶不做处理。

求中位数

如何求动态数据集合中的中位数，中位数就是中间位置的数。

（1）如果是奇数，中位数是n/2+1

（2）如果是偶数，中位数是n/2或者n/2+1

如果数据是动态的，中位数是固定的，我们可以把数据排序一次，然后取中位数即可。但如果数据是动态的，那就需要每次都排序了，效率不高。

使用堆就可以避免每次都排序了

具体做法：需要维护两个堆，一个大顶堆和一个小顶堆，大顶堆中存储前半部分的数据，小顶堆中存储后半部分的数据。如果数据为n，如果n为奇数大顶堆中存储n/2+1个元素，如果n为偶数，大顶堆中存储n/2个元素。大顶堆中的堆顶元素就是中位数了。

如果新插入的数据大于等于大堆顶的元素，就插入到大顶堆，如果新插入的数据大于等于小堆顶的元素，就插入到小顶堆

插入完后可能会造成元素的不平衡，就是上面的（1）（2），这时候根据（1）（2）中的要求移动一下数据即可（一个堆中的一个数据移到另一个堆中）。