一种特殊的树—堆

1 什么是堆？

堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。

2 堆的两个特性是什么？

ü 堆是一个完全二叉树；

堆必须是一个完全二叉树。完全二叉树要求，除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列。

ü 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。

堆中的每个节点的值必须大于等于（或者小于等于）其子树中每个节点的值。实际上，我们还可以换一种说法，堆中每个节点的值都大于等于（或者小于等于）其左右子节点的值。这两种表述是等价的。

3 什么是大顶堆和小顶堆？

大顶堆:大顶堆也称作为最大堆，对于每个节点的值都大于等于子树中每个节点值的堆。

小顶堆:小顶堆也称作为最小堆，对于每个节点的值都小于等于子树中每个节点值的堆。

4 什么是堆化？

把新插入的元素放到堆的最后，让其重新满足堆的特性，这个过程我们起了一个名字，就叫做堆化（heapify）。

5 如何实现一个堆？

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

往堆里插入一个元素

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;    }  } }

从堆中删除一个元素

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;  }}

6 堆的应用

  6.1 高性能定时器

    假设我们有一个定时器，定时器中维护了很多定时任务，每个任务都设定了一个要触发执行的时间点。定时器每过一个很小的单位时间（比如 1 秒），就扫描一遍任务，看是否有任务到达设定的执行时间。如果到达了，就拿出来执行。

    但是，这样每过 1 秒就扫描一遍任务列表的做法比较低效，主要原因有两点：第一，任务的约定执行时间离当前时间可能还有很久，这样前面很多次扫描其实都是徒劳的；第二，每次都要扫描整个任务列表，如果任务列表很大的话，势必会比较耗时。针对这些问题，我们就可以用优先级队列来解决。我们按照任务设定的执行时间，将这些任务存储在优先级队列中，队列首部（也就是小顶堆的堆顶）存储的是最先执行的任务。这样，定时器就不需要每隔 1 秒就扫描一遍任务列表了。它拿队首任务的执行时间点，与当前时间点相减，得到一个时间间隔 T。这个时间间隔 T 就是，从当前时间开始，需要等待多久，才会有第一个任务需要被执行。这样，定时器就可以设定在 T 秒之后，再来执行任务。从当前时间点到（T-1）秒这段时间里，定时器都不需要做任何事情。当 T 秒时间过去之后，定时器取优先级队列中队首的任务执行。然后再计算新的队首任务的执行时间点与当前时间点的差值，把这个值作为定时器执行下一个任务需要等待的时间。这样，定时器既不用间隔 1 秒就轮询一次，也不用遍历整个任务列表，性能也就提高了。

  6.2 求 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 大数据，我们都可以立刻返回给他

  6.3 求中位数

中位数即是处在中间位置的数，如果数据的个数是奇数，把数据从小到大排列，那第 2n​+1 个数据就是中位数（注意：假设数据是从 0 开始编号的）；如果数据的个数是偶数的话，那处于中间位置的数据有两个，第 2n​个和第 2n​+1 个数据，这个时候，我们可以随意取一个作为中位数，比如取两个数中靠前的那个，就是第 2n​个数据。

对于一组静态数据，中位数是固定的，我们可以先排序，第 2n​个数据就是中位数。每次询问中位数的时候，我们直接返回这个固定的值就好了。所以，尽管排序的代价比较大，但是边际成本会很小。但是，如果我们面对的是动态数据集合，中位数在不停地变动，如果再用先排序的方法，每次询问中位数的时候，都要先进行排序，那效率就不高了。

借助堆这种数据结构，我们不用排序，就可以非常高效地实现求中位数操作。我们需要维护两个堆，一个大顶堆，一个小顶堆。大顶堆中存储前半部分数据，小顶堆中存储后半部分数据，且小顶堆中的数据都大于大顶堆中的数据。

参考自：《数据结构与算法之美》