深入数据结构：“堆” #43

campcc · 2022-08-23T01:34:17Z

堆（Heap）是一种特殊的树，广泛应用于排序，搜索，优先级队列，求中位数等场景，接下来我将带你一起系统地学习，从原理，实现到应用全面地深入 “堆” 这个数据结构。

正式开始之前，你可以先思考一个问题，

如何在包含 10 亿个搜索关键词的日志文件中，快速获取到热门榜 Top 10 的搜索关键词呢？

这个场景在如今搜索引擎的热门搜索排行榜上非常常见，而我们接下来要介绍的 “堆” 这个数据结构就可以解决这个问题。

堆的定义

在介绍堆的定义之前，我觉得有必要先带你回顾下相关的一些知识，

二叉树：一种非线性表数据结构，每个节点最多有左、右两个子节点；
完全二叉树：除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列；
时间复杂度：衡量算法执行效率的一种方式，我们一般用大 O 复杂度表示法来表示，定义为 $T(n) = O(fn)$，其中 $n$ 表示数据规模的大小，$T(n)$ 表示代码执行的时间，与每行代码执行次数总和 $f(n)$ 成正比；在计算上，我们一般只关注循环执行次数最多的一段代码，忽略掉常量、低阶和系数，遵循加法法则和乘法法则；
原地排序：空间复杂度为 $O(1)$ 的排序

标准定义上，我们认为一颗树满足以下的两点，就是一个堆，

一颗完全二叉树
每个节点的值大于等于（或小于等于）其子树中每个节点的值

根据子节点与父节点值的大小关系，可以把堆分为，

最大堆（也叫大根堆，大顶堆），任意父节点都比其子节点的值要大
最小堆（也叫小根堆，小顶堆），任意父节点都比其子节点的值要小

比如上图中， 1、2 为最大堆，3 是最小堆，4 不是堆。

堆的实现

要实现一个堆，我们可以先思考，如何存储一个堆。

树的存储方式一般有链式存储和线性存储，分别对应我们常见的链表和数组两种方式，对于完全二叉树而言，用数组来存储是非常节省存储空间的，因为不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点，

所以堆我们一般也用数组来存储，

假设我们从数组下标 1 开始存储，不难发现，对于下标为 $i$ 的任意节点，存在以下关系，

// 其左子节点的索引满足
var leftIndex = 2 * i;
// 其右子节点的索引满足
var rightIndex = 2 * i + 1;
// 其父节点的索引满足
var parentIndex = i / 2;

为什么我们要从数组下标 1 开始存储，从 0 开始不行吗？

当然可以，如果从 0 开始存储，在代码的实现上，只是计算子节点和父节点的下标的公式改变了，对于下标为 $i$ 的任意节点，

// 其左子节点的索引满足
var leftIndex = 2 * i + 1;
// 其右子节点的索引满足
var rightIndex = 2 * i + 2;
// 其父节点的索引满足
var parentIndex = i - 1 / 2;

那为什么我们不从下标 0 开始存储呢？我想你应该已经猜到答案了，这里与 数组下标从 0 开始计数，而不是 1 开始 有着异曲同工之妙，我们从下标 1 开始存储，每次计算子节点和父节点时，都可以减少一次加法操作，本质是为了提高代码的性能。

知道了如何存储一个堆后，我们接着来看堆都支持哪些操作？

一般来说，堆有几个核心的操作，比如往堆中插入一个元素，删除堆顶元素。

堆的插入

往堆中插入一个元素后，为了保持堆的特性，我们需要对插入元素的位置进行调整，这个过程叫做堆化（heapify），以最大堆为例，

堆化的过程其实非常简单，比如上图中我们往最大堆中插入一个元素 “22”，为了保持堆的特性，只需要顺着节点所在的路径，向上与其父节点进行对比交换，直到满足大小关系即可，

class Heap {
  constructor(n) {
    this.a = new Array(n); // 存储堆的数组，从下标 1 开始存储数据
    this.n = n; // 堆可以存储的最大数据个数
    this.count = 0; // 堆中已经存储的数据个数
  }

  insert(data) {
    // 堆满直接返回
    if (this.count >= this.n) return;
    // 为了最大性能的存储堆，并保证堆中节点与数组下标的关系，我们从下标 1 开始存储数据，所以这里是 ++count
    ++this.count;
    // 从数组末尾插入，然后开始堆化（heapify），这里是最大堆，我们从下往上堆化
    // 堆化的过程就是：用当前节点与父节点做比较，大于父节点就交换，直到小于父节点为止
    this.a[count] = data;
    var i = count;
    while (i / 2 > 0 && this.a[i] > this.a[Math.floor(i / 2)]) {
      swap(this.a, i, Math.floor(i / 2));
      i = Math.floor(i / 2);
    }
  }
}

// 交换数组 a 中下标为 i 和 j 的元素
function swap(a, i, j) {
  var temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

往堆中插入数据我们解决了，如何从堆中删除数据呢？

堆的删除

堆中数据的删除我们可以先考虑删除堆顶元素。

从堆定义的第二条我们发现，堆顶元素存储的就是堆中数据的最大值或者最小值，以最大堆为例，最容易想到的是：删除堆顶元素后，把子节点中较大的元素放到堆顶，然后迭代地删除第二大节点，以此类推直到叶子节点被删除，

这种方式有没有什么问题呢？

从上图我们发现，删除后可能会出现数组空洞，而且最后堆化出来的堆并不满足完全二叉树的特性，有没有更好的办法呢？

这里我们可以尝试换一种思路，先删除叶子节点（最后一个元素），把它放到堆顶（与堆顶元素交换），然后从上往下进行堆化，

因为我们移除的是数组中的最后一个元素，而在堆化的过程中，都是交换操作，不会出现数组中的“空洞”，所以这种方法堆化之后的结果，肯定满足完全二叉树的特性，

// 从上往下堆化
function heapify(a, n, i) {
  while (true) {
    var 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;
  }
}

这样一来，删除堆顶元素就很简单了，

function removeMax() {
  if (count === 0) return -1;
  // 交换叶子节点和堆顶元素，然后从上到下进行堆化
  a[1] = a[count];
  --count;
  heapify(a, n, 1);
}

如果我们要删除堆中的任意一个节点的元素，应该怎么做呢？

类似的，我们只需要将数组的最后一个元素与要删除的节点元素互换，然后从要删除的节点开始从上往下堆化即可，这里你可以试着实现一下。

我们来讨论一下上面两个核心操作的时间复杂度。

首先，对于一个包含 $n$ 个节点的完全二叉树，树的高度不会超过 $\log_2{n}$，堆化的过程是顺着节点所在路径比较交换的，所以堆化的时间复杂度跟树的高度成正比，用大 O 复杂度表示法就是 O($\log{n}$)；我们发现插入和删除主要逻辑就是堆化，其他操作都是常数级别的，

所以往堆中插入一个元素和删除堆顶元素的时间复杂度都是 O($\log{n}$)。

存储，插入和删除我们都解决了，接下来我们来看如何构建一个堆，以及利用堆进行排序。

堆排序

我们知道堆排序是时间复杂度为 O($n\log{n}$) 的原地排序算法，具体是怎么实现的呢？

堆排序的过程大致可以分为两步，建堆和排序。

堆的构建

建堆意味着我们需要将数组原地构建成一个堆，一般有两种思路，

往堆中依次插入元素，我们假设起始堆中只包含一个数据，就是下标为 1 的数据，然后将下标从 2 到 $n$ 的数据依次插入到堆中
从最后一个非叶子节点开始，从上往下进行堆化

第一种思路是最容易想到的，我们需要遍历整个数组然后对每个数据进行插入操作，但时间复杂度较高，为 O($n\log{n}$)；第二种思路不太好理解，这里我们展开一下，

前面我们提到，对于完全二叉树，根据数组存储规律，不难发现下标 $\frac{n}{2} + 1$ 到 $n$ 的是叶子节点，下标 1 到 $\frac{n}{2}$ 是非叶子节点，叶子节点不需要堆化，这里我们只需要对非叶子节点进行堆化就可以构建堆，还是以最大堆为例，

我们从最后一个非叶子节点开始，从上往下进行堆化，

我把上述的过程翻译成了代码，你可以参考一下，

// 构建最大堆
function buildHeap(a, n) {
  // 根据完全二叉树数组存储的规律，下标为 1 到 n/2 的为非叶子节点
  // 为了保证堆的特性，我们从最后一个非叶子节点开始堆化
  for (var i = Math.floor(n / 2); i >= 1; --i) {
    heapify(a, n, i);
  }
}

// 从上往下堆化
function heapify(a, n, i) {
  while (true) {
    var 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;
  }
}

// 交换 a[i] 和 a[j]
function swap(a, i, j) {
  var temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

你能分析出上面这种建堆方式的时间复杂度是多少吗？

我们知道每个节点堆化的时间复杂度是 O($\log{n}$)，那 $\frac{n}{2} + 1$ 个节点堆化的总时间复杂度是不是就是 O($n\log{n}$) 呢？

实际上，建堆的时间复杂度是 O($n$)，为什么？我们来分析一下。

建堆的过程中叶子节点是不需要堆化的，所以需要堆化的节点是从倒数第二层开始，每一层我们需要比较和交换的次数，和树的高度成正比，

所以建堆的时间复杂度，就是除最后一层外，每层节点比较和交换的次数之和，

这个公式的求解非常简单，我们把公式左右都乘以 2 得到另一个公式 $S_2$，然后将 $S_1$ 和 $S_2$ 错位对齐求差值得到，

$S$ 的后面部分是等比数列，带入等比数列的求和公式，

前面提到树的高度 $h = \log_2{n}$，代入公式 $S$，就能得到 $S=O(n)$，

所以，建堆的时间复杂度是 $O(n)$。

堆排序

构建好堆后，排序就很简单了，我们发现数组中的第一个元素就是堆顶，也就是最大的元素，假设我们要从小到大对数据进行排序，应该怎么做呢？

是不是只需要把堆顶元素与最后一个元素（下标为 $n$ 的元素）进行交换，这样最大的元素就排到了数组末尾，接着通过堆化的方法，将剩下的 $n$−1 个元素重新构建成堆；然后再取堆顶的元素，与倒数第二个元素（下标是 $n$−1 的元素）交换，一直重复这个过程，直到最后堆中只剩下标为 1 的一个元素，排序工作就完成了，

// 堆排序
function heapSort(a, n) {
  buildHeap(a, n);
  var k = n;
  while (k > 1) {
    // 交换堆顶和最后一个元素
    swap(a, 1, k);
    --k;
    // 交换后只有堆顶元素不符合堆的特性，这里我们只需要对堆顶节点堆化即可，而不用重新构建整个堆
    heapify(a, k, 1);
  }
}

我们来分析一下堆排序的空间，时间复杂度和稳定性，

堆排序是原地排序吗？是，堆排序只需要存储极个别的变量，空间复杂度是 $O(1)$
堆排序的时间复杂度是多少？前面我们提到，堆排序分为建堆和排序两个过程，建堆是 $O(n)$，排序是 $O(n\log{n})$，根据加法法则，堆排序整体的时间复杂度为 $O(n\log{n})$
堆排序是稳定的排序算法吗？不是，排序的过程我们会将堆顶元素与最后一个元素交换，这里是有可能改变值相同数据的原始相对顺序的

好了，现在你应该对 “堆” 这种数据结构有一定的了解了，接下来我们来深入堆的一些应用。

堆的应用

堆除了可以实现复杂度稳定的 $O(n\log{n})$ 的堆排序外，还有几个非常经典的应用：求 Top K 、优先级队列和求中位数。

Top K 问题

求 Top K 问题可以抽象为两类，静态数据集合和动态数据集合。

针对静态数据，最经典的是，如何在包含 $n$ 个数据的数组中，查找前 $k$ 大的数据呢？

这里如果用堆来解决，思路是什么样的呢？我们可以维护一个大小为 $k$ 的最小堆，然后顺序遍历数组，从下标为 $k$ + 1 的元素开始，与堆顶元素进行比较，

如果比堆顶元素大，我们把堆顶元素删除，将这个元素插入到堆中
如果比堆顶元素小，则不做处理

这样数组遍历完后，堆中就是前 $k$ 大的数据，

// 交换元素
function swap(a, i, j) {
  var temp = a[i];
  a[i] = a[j];
  a[j] = temp;
}

// 堆化
function heapify(a, n, i) {
  while (true) {
    var minPos = i;
    if (2 * i <= n && a[i] > a[2 * i]) minPos = 2 * i;
    if (2 * i + 1 <= n && a[minPos] > a[2 * i + 1]) minPos = 2 * i + 1;
    if (minPos === i) break;
    swap(a, i, minPos);
    i = minPos;
  }
}

// 构建堆
function buildHeap(a, n) {
  for (var i = Math.floor(n / 2); i >= 1; --i) {
    heapify(a, n, i);
  }
  return a;
}

// 利用堆求 Top K 问题
function findTopK(a, k) {
  // 从数组下标 1 开始构建堆，减少一次获取节点时的加法操作
  a.unshift(null);
  var len = a.length;
  // 构建 k 个元素的最小堆
  var minHeap = buildHeap(a, k);
  // 从第 k + 1 个元素开始比较，如果大于堆顶元素，替换堆顶元素，再次构建堆
  // 这里和之前思路一样，替换堆顶元素后只有堆顶元素不符合堆的特性，所以我们不需要重新构建整个堆，只需要对堆顶元素再次堆化即可
  for (var i = k + 1; i < len; i++) {
    if (a[i] > minHeap[1]) {
      swap(minHeap, i, 1);
      heapify(minHeap, k, 1);
    }
  }
  // 当前堆的 (1, k + 1) 元素就是 topk
  var topk = minHeap.slice(1, k + 1);
  return topk;
}

// var a = [7, 5, 19, 8, 4, 1, 20, 13, 16, 33, 44, 5, 3, 1, 2, 23];
// var topk = findTopK(a, 5);
// console.log(topk);

上面利用堆求 Top K 的时间复杂度是多少呢？我们来简单分析一下，

首先这里我们只对 $k$ 个元素构建了最小堆，每次堆化的时间复杂度为 $O(\log{k})$，建堆 $(0, k)$ 和遍历数组 $(k + 1, n)$ 整体的时间复杂度为 $O(n)$，所以通过上述方式求 Top K 的时间复杂度为 $O(n\log{k})$，其中 $n$ 是静态数据的大小。

当然，实际的应用场景中我们可能会遇到动态数据集合，如何针对动态数据求 Top K 呢？

动态数据求 Top K 其实就是求实时 Top K，想象一下，如果我们每次都基于当前动态数据重新去计算的话，那时间复杂度就是 $O(n\log{k})$；有没有什么办法能更高效地查询 Top K 呢？

有。实际上，我们可以一直维护一个大小为 $k$ 的最小堆，当有数据被添加到集合中时，我们就拿它与堆顶元素进行对比，跟前面类似的，

如果比堆顶元素大，把堆顶元素删除，将这个元素插入到堆中
如果比堆顶元素小，则不做处理

这样，每次数据添加的时候，其实只做了一次常数级别的堆化处理，带来的好处是，无论任何时候查询 Top K，我们都可以在 $O(1)$ 的时间复杂度内立即返回。

优先级队列

与普通队列的先进先出（FIFO）不同，优先级队列队列中，数据的出队顺序是按照优先级来的，优先级最高的，最先出队。

我们知道优先级队列的应用场景非常多，而且很多的数据结构和算法（比如赫夫曼编码、图的最短路径、最小生成树算法等）都依赖它，那如何实现一个优先级队列呢？

毋庸置疑，最直接、最高效的方式是通过堆来实现，因为堆本身就可以看作一个优先级队列，

往优先级队列中插入数据，就相当于往堆中插入一个元素
从优先级队列中取出优先级最高的元素，就相当于取出堆顶元素

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

但这样每过 1 秒就扫描一遍任务列表的做法其实是比较低效的，为什么？

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

如何优化这个定时器，让它具有更高的性能呢？

我们可以将任务存储在优先级队列（最小堆）中，堆顶的元素就是最先执行的任务，我们取堆顶任务拿到首个任务的执行时间点，然后与当前时间点相减，得到一个时间间隔 $T$，这样定时器就可以设定在 $T$ 秒之后，等 $T$ 秒时间过去之后，定时器取优先级队列中队首的任务执行，然后再计算新的队首任务的执行时间点与当前时间点的差值 $T_1$，创建新的定时器，这样定时器就不需要每隔 1 秒轮询列表了，

// 任务列表
var taskList = [
  { name: 'taskA', timestamp: '2022-08-22 10:00:00', run: () => console.log('taskA run') },
  { name: 'taskB', timestamp: '2022-08-22 10:03:00', run: () => console.log('taskB run') },
  { name: 'taskC', timestamp: '2022-08-22 10:05:00', run: () => console.log('taskC run') },
];

// 构建最小堆
var minHeap = buildHeap(taskList, taskList.length);

// 利用堆模拟高性能定时器
function timer() {
  // 计算下一个出队任务的时间间隔
  var T = calcInterval(minHeap[1].timestamp, Date.now());
  setTimeout(() => {
    // 取堆顶任务出队执行
    var task = minHeap.shift();
    task.run();
    // 交换最后一个任务到堆顶，重新构建堆
    swap(minHeap, 1, minHeap.length - 1);
    heapify(minHeap, minHeap.length, 1);
    // 开启下一轮定时
    timer();
  }, T);
}

求中位数

对于静态数据，中位数是固定的，我们可以先排序，第 $\frac{n}{2}$ 个数据就是中位数，尽管排序的代价较大，但边际成本是很小的，但对于动态数据集合而言，中位数在不停地变动，我们再使用上面的方式效率就很低了，如何高效地求动态数据集合中的中位数呢？

这里我们可以维护两个堆，一个最大堆，一个最小堆，假设有 $n$ 个数据，我们可以从小到大进行排序，将前 $\frac{n}{2}$（n为偶数）或 $\frac{n}{2} + 1$（n为奇数）个数据存储在最大堆中，剩余数据存储在最小堆中，这样最大堆的堆顶元素就是我们要求的中位数。

现在的问题是，数据是动态变化的，当新添加一个数据的时候，我们该如何调整两个堆，让最大堆中的堆顶元素继续是中位数呢？

这里我们可以考虑新添加数据的大小关系来判断到底应该插入到哪一个堆，

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

需要注意的是，为了满足两个堆中数据个数的存储约定，插入数据后，我们需要从一个堆中将堆顶元素搬移到另一个堆，保证最大堆中的元素个数满足，

$n$ 为偶数时，元素个数为 $\frac{n}{2}$
$n$ 为奇数时，元素个数为 $\frac{n}{2} + 1$

// 求动态数据集合中的中位数
class MedianFinder {
  constructor(a, n) {
    // 从小到大排序，然后初始化两个堆，最大堆存储前 n/2 个元素，最小堆存储剩余元素
    a.sort((i, j) => i - j < 0);
    this.maxHeap = buildHeap(a, n / 2);
    this.minHeap = buildHeap(a, n / 2 + 1);
  }

  // 往堆中添加元素
  push(a, data) {
    a.push(data);
    // 交换至堆顶，然后进行堆化
    swap(a, 1, a.length - 1);
    heapify(a, a.length, 1);
  }

  // 添加新元素
  add(data) {
    if (data <= this.maxHeap[1]) {
      this.push(this.maxHeap, data);
    } else {
      this.push(this.minHeap, data);
    }
    // 调整两个堆，让存储的元素个数满足约定
    if (this.maxHeap.length - this.minHeap.length > 1) {
      var last = this.maxHeap.pop();
      this.push(this.minHeap, last);
    } else {
      var last = this.minHeap.pop();
      this.push(this.maxHeap, last);
    }
  }

  // 获取中位数
  findMedian() {
    return this.maxHeap[1];
  }
}

以上是常见的堆的一些典型应用，当然除了最大堆和最小堆，还有二项堆，斐波那契堆等等，它们适用于一些特殊的场景，有兴趣的同学可以去了解下，最后让我们来解答开篇的问题，如何在包含 10 亿个搜索关键词的日志文件中，快速获取到热门榜 Top 10 的搜索关键词？

当然，这里有很多其他高级的解决方案，比如 MapReduce，我们重点来分析下如何通过堆来解决这个问题。

首先用户的搜索关键字可能是重复的，这里我们可以先通过散列表，顺序扫描这 10 亿个搜索关键词，当扫描到某个关键词时，

如果存在，我们将散列表中对应的次数加一
如果不存在，我们将它插入到散列表，并记录次数为 1

然后，根据前面讲的用堆求 Top K 的方法，建立一个大小为 10 的小顶堆，遍历散列表，依次取出每个搜索关键词及对应出现的次数，接着与堆顶的搜索关键词进行对比。如果出现次数比堆顶搜索关键词的次数多，删除堆顶的关键词，将这个出现次数更多的关键词加入到堆中，

// 从 10 亿搜索关键词的日志文件中，获取热门榜 Top K 的搜索关键词
function findTopk(a, k) {
  // 扫描搜索关键词，构建散列表
  var map = new Map();
  for (var keyword of a) {
    if (map.has(keyword)) {
      map.set(keyword, map.get(keyword) + 1);
    } else {
      map.set(keyword, 1);
    }
  }
  // 构建大小为 k 的最小堆
  var minHeap = buildHeap([...map].slice(0, k), k);
  // 遍历散列表，如果遍历到的搜索关键词的出现次数比当前堆顶元素的出现次数大，替换堆顶元素，重新构建堆
  map.entries((keyword, count) => {
    var top = minHeap[1];
    if (count > top[1]) {
      minHeap.push([keyword, count]);
      swap(minHeap, 1, minHeap.length - 1);
      heapify(minHeap, minHeap.length, 1);
    }
  });
  // 散列表遍历完成后，当前的堆就是我们要求的热门榜 Top K
  return minHeap.map((keywordMap) => keywordMap[0]);
}

参考链接

写在最后

本文首发于我的博客，才疏学浅，难免有错误，文章有误之处还望不吝指正！

如果有疑问或者发现错误，可以在评论区进行提问和勘误，

如果喜欢或者有所启发，欢迎 star，对作者也是一种鼓励。

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

深入数据结构：“堆” #43

深入数据结构：“堆” #43

campcc commented Aug 23, 2022

深入数据结构：“堆” #43

深入数据结构：“堆” #43

Comments

campcc commented Aug 23, 2022

堆的定义

堆的实现

堆的插入

堆的删除

堆排序

堆的构建

堆排序

堆的应用

Top K 问题

优先级队列

求中位数

参考链接

写在最后