数据结构与算法之美-堆的应用

前言：本篇文章只是记录王争的数据结构与算法之美的学习笔记，写下来能强迫自己系统的再过一遍，加深理解。这门课以实际开发中遇到的问题为例，引入解决问题涉及到的的数据结构和算法，但不会讲的太细，最好结合一本实体书进行学习。

1. 堆的概念

堆是一种特殊的树，需要满足下面两点：

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

大顶堆和小顶堆就是根据第二条区分的：

• 每个节点的值都大于等于子树中每个节点值的堆为大顶堆
• 每个节点的值都小于等于子树中每个节点值的堆为小顶堆

如下图：

image.png

2. 堆的实现

2.1 堆的存储

上面说堆是一个完全二叉树，完全二叉树比较适合用数组来存储。用数组存储完全二叉树节省内存空间，单纯的通过数组下标，就可以找到一个节点的左右子节点和父节点，如下图所示：

image.png

从上图中可以看到：

• 数组中下标为 i 的节点的左子节点的下标为i * 2
• 右子节点就是下标为i * 2 + 1的节点
• 父节点就是下标为i / 2的节点

2.2 堆中插入一个元素

如果把新插入的元素放到堆的最后，如果不符合堆的特性，就需要调整，调整的过程称为堆化。如下图所示：

image.png

堆化就是顺着节点所在的路径，向上或者向下，对比，然后交换，所以堆化分为两种：

• 从下往上
• 从上往下

以从下往上为例，堆化的过程就是让新插入的节点和父节点对比大小，如果不满足子节点小于等于父节点的关系，就互换两个结点，一直重复这个过程，直到满足，如下图所示：

image.png

代码实现如下：

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.3 删除堆顶元素

堆顶元素就是堆中数据的最大值或者最小值。

删除操作过程：把最后一个节点放到堆顶，然后利用同样的父子节点对比方法，对于不满足父子节点大小关系的，互换两个节点，并且重复此过程，直到父子节点之间满足大小关系为止。

这就是从上往下的堆化方法，如下图所示：

image.png

代码如下：

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

一个包含 n 个节点的完全二叉树，树的高度不会超过log2n，堆化的过程是顺着节点所在路径比较交换的，所以堆化的时间复杂度是 O(logn)。插入一个元素和删除堆顶元素的主要逻辑就是堆化，时间复杂度都是O(logn)。

3. 基于堆实现排序

基于堆这种数据结构实现的排序算法叫做堆排序，时间复杂度非常稳定，是 O(nlogn)，并且还是原地排序算法。

堆排序的过程大致分为 两个步骤：建堆 和 排序。

3.1 建堆

首先需要将数组原地建成一个堆，有两种思路：

• 第一种跟堆中插入一个元素一样，起初堆中只包含一个数据，下标为 1，然后用前面的插入操作，将2 到 n 的数据依次插入到堆中，从前往后处理数组数据，并且每个数据插入堆中时，都是从下往上堆化
• 第二种跟第一种截然相反，是从后往前处理数组，并且每个数据都是从上往下堆化

第二种实现思路的分解图：

image.png image.png

实现代码：

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

代码中只对下标从1到 n/2的数据进行了堆化，因为对于完全二叉树来说，下标从n/2 + 1 到 n 的节点都是叶子结点。

完全二叉树中最后一个节点的下标为 n，那么其父节点就是最后一个非叶子结点，下标为 n/2 ，之后的节点都是叶子结点了，也就是n/2 + 1 到 n 的节点都是叶子节点。

建堆的时间复杂度：
堆排序的建堆过程的时间复杂度是 O(n)。

推导过程：
叶子节点不需要堆化，所以需要堆化的节点从倒数第二层开始，每个节点堆化的过程中，需要比较和交换的节点个数，跟这个节点的高度 k 成正比。

下图把每一层的节点个数和对应的高度画了出来，我们只需要将每个节点的高度求和，得出的就是建堆的时间复杂度：

image.png

将每个非叶子节点的高度求和，就是下面的公式：

image.png image.png

最终的结果就是：

image.png

因为 h = log2n，带入公式，得到 S = O(n)，所以建堆的时间复杂度就是 O(n)。

3.2 排序

排序主要使用了类似“删除堆顶元素”的操作，因为数组中第一个元素就是堆顶，也是最大的元素，把堆顶元素放到下标为 n 的位置，然后再通过堆化方法，将剩下 n - 1个元素重新构建成堆。堆化完成之后，我们再取堆顶的元素，放到下标是 n−1 的位置，一直重复这个过程，直到最后堆中只剩下标为 1 的一个元素，排序工作就完成了。如下图：

image.png

代码如下：

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

3.3 堆排序分析

堆排序是原地排序算法，只需要极个别临时存储空间。
堆排序包括建堆和排序两个操作，建堆的时间复杂度是 O(n)，排序的时间复杂度是O(nlogn)，所以，堆排序整体的时间复杂度是 O(nlogn)。

堆排序不是稳定的排序算法，因为在排序的过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序。

为什么快排要比堆排序性能好？

• 堆排序数据访问的方式没有快排友好
  快排是顺序访问的，堆排序数据是跳着访问的，对 CPU 缓存不友好
• 对于同样的数据，在排序过程中，堆排序算法的数据交换次数要多于快速排序

4. 堆的应用

4.1 优先级队列

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

4.1.1 合并有序小文件

场景：有 100 个小文件，大小都是 100MB，存储的都是有序的字符串，想将这些 100 个小文件合并成一个有序的大文件。

就需要用到优先级队列，也可以说是堆。先从 100 个文件中，各取第一个字符串，然后构建一个小顶堆，堆顶的元素也就是优先级队列队首的元素，就是最小的字符串。将这个字符串放入到大文件中，然后将其从堆中删除。然后再从那个小文件中取出下一个字符串，放入到堆中，循环这个过程就可以了。

4.1.2 高性能定时器

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

image.png

这样每隔 1 秒就扫描一遍任务列表比较低效。我们可以使用优先级队列来解决：

• 按照任务设定的时间，将这些任务存储在优先级队列中，队列首部（小顶堆的堆顶）存储的是最先执行的任务
• 定时器就每次拿到队首任务的执行时间点，和当前时间点相减，得到一个时间间隔 T，定时器设定在 T 秒之后，执行任务
• 队首任务执行完成之后，再计算新的队首任务的执行时间点和当前时间点的差值，把这个值作为定时器执行下一个任务需要等待的时间
• 直到任务都完成

4.2 利用堆求 Top K

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

• 针对静态数据集合(数据集合事先已经确定，不会再变)
• 针对动态数据集合(数据集合可能会再添加新的数据)

针对于一个 n 个数据的数组，要查找前 K 大数据：

• 1.维护一个大小为 K 的小顶堆
• 2.顺序遍历数组，和堆顶元素比较
• 3.如果比堆顶元素大，就把堆顶元素删除，将这个元素插入到堆中
• 4.如果比堆顶元素小，就继续遍历
• 5.遍历完成之后，小顶堆中的数据就是前 K 大数据了

遍历数组的时间复杂度为 O(n)，堆化的时间复杂度为 O(logK)，所以最坏的时间复杂度就是O(nlogK)。

针对于动态数据求 Top K 就是实时获取 TopK，其中有两个操作，一个是添加数据，另一个获取当前的前 K 大数据。
可以一直维护一个 K 大小的小顶堆，当有数据被添加到集合中时，和堆顶的元素进行对比，进行堆化。

4.3 求中位数

就是求动态数据集合中的中位数，如下图：

image.png

针对于静态数据：

• 中位数是固定的，先进行排序
• 获取第n/2 个数据就是中位数

针对于动态数据：

• 维护两个堆：一个大顶堆 & 一个小顶堆
• 大顶堆存储前半部分数据，小顶堆存储后半部分数据，并且小顶堆中的数据都大于大顶堆中的数据

如果有 n 个数据：

• n 是偶数，从小到大排序，前 n/2 个数据存储在大顶堆中，后n/2个数据存储在小顶堆中，大顶堆中的堆顶元素就是中位数
• n 是奇数，大顶堆存储 n/2 + 1 个元素，小顶堆存储 n/2个数据

image.png

当有数据要加入的时候，需要调整两个堆：

• 如果新加入的数据小于等于大顶堆的堆顶元素，就插入到大顶堆
• 否则，插入到小顶堆
• 如果出现两个堆中数据个数不符合前面的情况，需要从一个堆中取堆顶元素移动到另一个堆，调整堆中数据

image.png

时间复杂度分析：

• 插入数据涉及到堆化，时间复杂度为 O(logn)
• 求中位数直接取大顶堆的堆顶元素，为 O(1)

5. 思考题

假设现在我们有一个包含 10 亿个搜索关键词的日志文件，如何能快速获取到热门榜 Top 10 的搜索关键词？场景限定为单机，可以使用的内存为 1GB。

• 1.将 10 亿条搜索关键词通过哈希算法分片到 10 个文件中
  构建 10 个空文件，从 0-9 编号，对10 亿个关键词通过哈希算法求哈希值，然后同 10 取模，存储到对应编号的文件中
• 2.利用散列表存储关键词及其出现的次数（遍历文件中的关键词，存入散列表中），每个文件对应维护一个小顶堆获取 top10，10 个文件，一共 10 个 top10
• 3.将这个 10 个 top10 放一块，取这 100 个关键词中，次数最多的 10 个关键字即可

6. 练习

• 堆的插入和删除
• 堆排序的实现
• 求 topk
• 求中位数
• 高效定时器
• 大文件的关键字统计