# 堆

# 什么是堆

堆是一种特殊的树。一棵树只要满足这两点，它就是一个堆：

堆是一个完全二叉树；
堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值；

对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作“小顶堆”。

# 如何实现一个堆

我们先要知道：

堆都支持哪些操作；
如何存储一个堆；

# 储存一个堆

之前讲过，完全二叉树比较适合用数组来存储。用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。

数组中下标为 $i$ 的节点的左子节点，就是下标为 $i∗2$ 的节点；
右子节点就是下标为 $i∗2+1$ 的节点；
父节点就是下标为 $i/2$ 的节点；

# 插入元素

插入操作的第一步是：新插入的元素放到堆的最后。

但此时，可能就不满足堆的特性了。所以需要进行一系列的操作，使其继续满足堆的两个特性。这个过程叫做堆化（heapify）。

在做 “插入操作” 的时候，我们做 “从下往上的堆化”。

让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系，我们就互换两个节点。一直重复这个过程，直到父子节点之间满足刚说的那种大小关系。


public class Heap {
  private int[] a;
  // 堆可以存储的最大数据个数
  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]) {
      // 交换下标为 i 和 i/2 的两个元素
      swap(a, i, i/2);
      i = i/2;
    }
  }
}

# 删除元素

在做 “删除操作” 的时候依旧需要堆化，在这里我们做 “从上往下的堆化”。

把最后一个节点替换到被删除节点的位置；
然后用父子节点对比的方法。对于不满足父子节点大小关系的，互换两个节点；
重复上面这个过程，直到父子节点之间满足大小关系为止；

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

// 自上往下堆化
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;
  }
}

# 基于堆实现排序

借助于堆这种数据结构实现的排序算法，就叫作堆排序。这种排序方法的时间复杂度非常稳定，是 $O(nlogn)$ ，

堆排序的过程大致分解成两个大的步骤：

建堆；
排序；

# 建堆

首先将数组原地建成一个堆。所谓 “原地” 就是，不借助另一个数组，就在原数组上操作。

建堆的过程，有两种思路：

# 从下往上建堆

第一种是借助我们前面讲的，在堆中插入一个元素的思路。尽管数组中包含 n 个数据，但是我们可以假设，起初堆中只包含一个数据，就是下标为 1 的数据。然后，我们调用前面讲的插入操作，将下标从 2 到 n 的数据依次插入到堆中。这样我们就将包含 n 个数据的数组，组织成了堆。

这种建堆思路的处理过程是从前往后处理数组数据，并且每个数据插入堆中时，都是从下往上堆化。

# 从上往下堆化

第二种实现思路，是从后往前处理数组，并且每个数据都是从上往下堆化。

(下图中，因为叶子节点往下堆化只能自己跟自己比较，所以我们直接从第一个非叶子节点 8 开始。图中，13，14，4，1，20 都是叶子节点。)

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

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+1$ 到 $n$ 的节点都是叶子节点。

# 排序

建堆结束之后，数组中的数据已经是按照大顶堆的特性来组织的。

数组中的第一个元素就是堆顶，也就是最大的元素。我们把它跟最后一个元素交换，那最大元素就放到了下标为 n 的位置；
当堆顶元素移除之后，我们把下标为 n 的元素放到堆顶，然后再通过堆化的方法，将剩下的 n−1 个元素重新构建成堆；
再取堆顶的元素，放到下标是 n−1 的位置，一直重复这个过程，直到最后堆中只剩下标为 1 的一个元素，排序工作就完成了；

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

堆排序包括建堆和排序两个操作，建堆过程的时间复杂度是 $O(n)$ ，排序过程的时间复杂度是 $O(nlogn)$ ，所以，堆排序整体的时间复杂度是 $O(nlogn)$ 。

# 堆的应用

堆这种数据结构几个非常重要的应用：优先级队列、求 Top K 和求中位数。

# 优先级队列

队列最大的特性就是先进先出。但在优先级队列中，数据的出队顺序不是先进先出，而是按照优先级来，优先级最高的，最先出队。

堆和优先级队列非常相似。一个堆就可以看作一个优先级队列。往优先级队列中插入一个元素，就相当于往堆中插入一个元素；从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素。

下面举两个优先级队列的应用：

# 合并有序小文件

假设我们有 100 个小文件，每个文件的大小是 100MB，每个文件中存储的都是有序的字符串。我们希望将这些 100 个小文件合并成一个有序的大文件。这里就会用到优先级队列。

# 高性能定时器

假设我们有一个定时器，定时器中维护了很多定时任务，每个任务都设定了一个要触发执行的时间点。

常规想法是，定时器每过一个很小的单位时间（比如 1 秒），就扫描一遍任务，看是否有任务到达设定的执行时间。如果到达了，就拿出来执行。

但是，这样每过 1 秒就扫描一遍任务列表的做法比较低效，主要原因有两点：

第一，任务的约定执行时间离当前时间可能还有很久，这样前面很多次扫描其实都是徒劳的；
第二，每次都要扫描整个任务列表，如果任务列表很大的话，势必会比较耗时；

用优先级队列来解决。我们按照任务设定的执行时间，将这些任务存储在优先级队列中，队列首部（也就是小顶堆的堆顶）存储的是最先执行的任务。

这样，定时器就不需要每隔 1 秒就扫描一遍任务列表了。它拿队首任务的执行时间点，与当前时间点相减，得到一个时间间隔 T。

这个时间间隔 T 就是，从当前时间开始，需要等待多久，才会有第一个任务需要被执行。这样，定时器就可以设定在 T 秒之后，再来执行任务。

当 T 秒时间过去之后，定时器取优先级队列中队首的任务执行。然后再计算新的队首任务的执行时间点与当前时间点的差值，把这个值作为定时器执行下一个任务需要等待的时间。

# 利用堆求 Top K

求 Top K 的问题抽象成两类：

针对静态数据集合，也就是说数据集合事先确定，不会再变；
针对动态数据集合，也就是说数据集合事先并不确定，有数据动态地加入到集合中；

# 针对静态数据

针对静态数据，如何在一个包含 n 个数据的数组中，查找前 K 大数据呢？

我们可以维护一个大小为 K 的小顶堆;
顺序遍历数组，从数组中取出数据与堆顶元素比较。如果比堆顶元素大，我们就将这个元素插入到堆中；
如果比堆顶元素小，则不做处理，继续遍历数组;
等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了；

遍历数组需要 $O(n)$ 的时间复杂度，一次堆化操作需要 $O(logK)$ 的时间复杂度，所以最坏情况下， $n$ 个元素都入堆一次，时间复杂度就是 $O(nlogK)$ 。

# 针对动态数据

针对动态数据求得 Top K 就是实时 Top K。怎么理解呢？举一个例子。一个数据集合中有两个操作，一个是添加数据，另一个询问当前的前 K 大数据。

如果每次询问前 K 大数据，我们都基于当前的数据重新计算的话，那就和上面处理静态数据一样，时间复杂度就是 $O(nlogK)$ ，n 表示当前的数据的大小。

但聪明的做法是：

可以一直都维护一个 K 大小的小顶堆；
当有数据被添加到集合中时，我们就拿它与堆顶的元素对比。如果比堆顶元素大，我们就将这个元素插入到堆中；
如果比堆顶元素小，则不做处理；
这样，无论任何时候需要查询当前的前 K 大数据，我们都可以立刻返回给他；

# 利用堆求中位数

对于一组静态数据，中位数是固定的，我们可以先排序，第 2n 个数据就是中位数。每次询问中位数的时候，我们直接返回这个固定的值就好了。

但是，如果我们面对的是动态数据集合，中位数在不停地变动，如果再用先排序的方法，每次询问中位数的时候，都要先进行排序，那效率就不高了。

借助堆，不用排序，就可以非常高效地实现求中位数操作。

我们需要维护两个堆，一个大顶堆，一个小顶堆。大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。

也就是说，如果有 n 个数据，n 是偶数，我们从小到大排序，那前 $n/2$ 个数据存储在大顶堆中，后 $n/2$ 个数据存储在小顶堆中。这样，大顶堆中的堆顶元素就是我们要找的中位数。如果 n 是奇数，情况是类似的，大顶堆就存储 $n/2+1$ 个数据，小顶堆中就存储 $n/2$ 个数据。

如果新加入的数据小于等于大顶堆的堆顶元素，我们就将这个新数据插入到大顶堆；否则，我们就将这个新数据插入到小顶堆。

这个时候就有可能出现，两个堆中的数据个数不符合前面约定的情况。我们需要从一个堆中不停地将堆顶元素移动到另一个堆，通过这样的调整，来让两个堆中的数据满足上面的约定。

于是，我们就可以利用两个堆，一个大顶堆、一个小顶堆，实现在动态数据集合中求中位数的操作。

插入数据因为需要涉及堆化，所以时间复杂度变成了 $O(logn)$ ，但是求中位数我们只需要返回大顶堆的堆顶元素就可以了，所以时间复杂度就是 $O(1)$ 。