登录
Hello，算法：微博热搜的背后
每个系列一本前端好书，帮你轻松学重点。
本系列来自上海交通大学硕士，华为高级算法工程师 靳宇栋 的 《Hello，算法》
截至本文编辑时，hello-algo项目Star数已飙升至122k，文末参与活动，获赠微信读书付费会员。
每天一睁眼，新闻头条、微博热搜都能抓住很多人的目光，购物时也会有商品排行榜，它们无形中对我们的注意力和决策产生重要影响。
那么，生活中随处可见的排行榜，在程序里如何做到，算法又叫什么呢？
它就是“Top-K”。什么是“Top-K”?
给定一个长度为n的无序数组 nums ，返回数组中最大的K个元素。
怎样从海量数据中找出Top-K？
直觉
1、遍历
从所有数据中找，每轮找出剩余数据中最大的。比如：
1 10 3 5 13 7 9 15 18
这样一组数，找出Top3的步骤：第一轮找出18，第二轮找出15，第三轮找出13，以此类推，要找Top几就要找几轮，时间复杂度为 O(n²)。
2、先排后选
既然要找Top-K，把整个都排一遍，变成有序的，再从中取前K个，也能达到目的。
这种方案的时间复杂度为 O（nlog n）。
可能还有人对复杂度没有概念，我们直观比较一下：
| 数据量(n) | O(n log n) | O(n²) | 倍差 |
|---|---|---|---|
| 10 | ~33 | 100 | 3倍 |
| 100 | ~664 | 10,000 | 15倍 |
| 1,000 | ~9,966 | 1,000,000 | 100倍 |
| 10,000 | ~132,877 | 100,000,000 | 752倍 |
| 100,000 | ~1,660,964 | 10,000,000,000 | 6,018倍 |
这么看，随着数量级的跃升，方案二优势越来越大，提升已经十分明显。
还有优化空间么？
痛点
1、遍历方案
简单，但效率低。只有在待排数量K和总数N之间差距较大时，能勉强接受，如果K和N接近，时间复杂度就趋向于O（n²），非常耗时。
2、先排后选
看起来已经不错，但不难发现，我们要找的是Top-K，不是Top-N，它做了多余的工作。
当K和N的差距越大，多余工作越多，二者相等时，就是纯排序了。
此外，实际上对我们有用的只是前K个元素，而不是全部的N个元素，这种方案对内存也造成浪费。
可见，从直觉而来的方法，虽然易上手，但不够好，我们要做的，就是 “升级”直觉。
那么，谁最适合用来解决Top-K问题？
初识“堆”
关于“堆”，其实你也很熟悉，“土堆、沙子堆、垃圾堆”，下面要讲的“堆”和它们没有本质区别。就像这样：
你可能会说：这不是树吗？
没错，通常来说，树应该是根在下，叶子在上，但在算法中一般是倒过来看，倒过来后它本身就很像是一个，堆...
堆是一种满足特定条件的完全二叉树，问题来了，什么是“完全二叉树”...打住！
我们不能陷入由一个问题带来另一个问题的循环中，只需要关注当下的关键目标。
堆满足的特定条件是：节点间需要固定的相对大小关系，一个节点要么比父大，要么比父小，由此划分为“大顶堆”和“小顶堆”。
形成了堆的特点，它就能发挥自己独有的威力。
很多编程语言都提供了“堆”的数据结构，称作“Heap”，遗憾的是，JavaScript中并没有。
为什么是它
“堆”结构有什么优势，为什么它是实现Top-K的最佳方案？
原理如下：
- 初始化一个小顶堆，其堆顶元素最小。
- 将前 k 个元素依次入堆。
- 从第 k + 1 个元素开始，若当前元素大于堆顶元素，则将堆顶元素出堆，并将当前元素入堆。
- 遍历完成后，堆中保存的就是最大的 k 个元素。
这4个步骤，弥补了上述方案的短板：
- 不需要维护 N 个元素
- 不需要遍历 K 轮
- 支持动态更新，且效率很高
核心代码
你应该还记得上篇文用数组实现的“哈希”，本篇亦然（一点都不意外~）
可是数组只有一对一的“索引”和“值”，怎么构造成堆呢？需要将其中的元素代表节点值，索引代表节点的位置。节点指针则通过索引映射公式来实现。
为方便使用，我们将映射公式封装成函数：
/* 获取左子节点的索引 */
left(i) {
return 2 * i + 1;
}
/* 获取右子节点的索引 */
right(i) {
return 2 * i + 2;
}
/* 获取父节点的索引 */
parent(i) {
return Math.floor((i - 1) / 2); // 向下整除
}
这些公式什么意思，又是怎么来的？具体表现如下图所示：
公式描述的是，给定一个节点 i，通过它来定位“左、右、父”节点。这里只关心位置和索引，跟值无关。
当堆结构形成后，就可以进行相关操作了。
主要关注：入堆和出堆。
因为它们可能打破堆结构已经形成的平衡，要做出调整来重新获得平衡。
入堆
关键步骤：
- 将新元素添加至堆底，即数组中新增一个元素；
- 新增元素可能小于堆顶的元素，也可能大于，小的时候不用动，如果大，则需要自底向上一路比较，这个操作称作“堆化”。
- 堆化的过程就是在做逐层比较和交换，直至越过根节点或遇到无须交换的节点，结束。
/* 元素入堆 */
push(val) {
// 添加节点
this.maxHeap.push(val);
// 从底至顶堆化
this.siftUp(this.size() - 1);
}
/* 从节点 i 开始，从底至顶堆化 */
siftUp(i) {
while (true) {
// 获取节点 i 的父节点
const p = this.parent(i);
// 当“越过根节点”或“节点无须修复”时，结束堆化
if (p < 0 || this.maxHeap[i] <= this.maxHeap[p]) break;
// 交换两节点
this.swap(i, p);
// 循环向上堆化
i = p;
}
}
入堆这么麻烦，出堆是不是就容易了，直接删掉？
当然不是，堆中的元素都存在着相互关联，直接删掉带来的结果是，其余所有元素都要发生变化，这不是明智的做法。
出堆操作也分为以下几步：
- 交换堆顶元素与堆底元素（根节点与最右叶节点）。
- 将堆底元素从列表中删除（注意，由于已经交换，因此实际上删除的是原来的堆顶元素）。
- 从根节点开始，从顶至底执行堆化。
/* 元素出堆 */
pop() {
// 判空处理
if (this.isEmpty()) throw new Error('堆为空');
// 交换根节点与最右叶节点（交换首元素与尾元素）
this.swap(0, this.size() - 1);
// 删除节点
const val = this.maxHeap.pop();
// 从顶至底堆化
this.siftDown(0);
// 返回堆顶元素
return val;
}
/* 从节点 i 开始，从顶至底堆化 */
siftDown(i) {
while (true) {
// 判断节点 i, l, r 中值最大的节点，记为 ma
const l = this.left(i),
r = this.right(i);
let ma = i;
if (l < this.size() && this.maxHeap[l] > this.maxHeap[ma]) ma = l;
if (r < this.size() && this.maxHeap[r] > this.maxHeap[ma]) ma = r;
// 若节点 i 最大或索引 l, r 越界，则无须继续堆化，跳出
if (ma === i) break;
// 交换两节点
this.swap(i, ma);
// 循环向下堆化
i = ma;
}
}
Top-K的堆实现
看完了入堆和出堆代码，来完整看一下基于堆寻找最大 K 元素的示例代码。
/* 元素入堆 */
function pushMinHeap(maxHeap, val) {
// 元素取反
maxHeap.push(-val);
}
/* 元素出堆 */
function popMinHeap(maxHeap) {
// 元素取反
return -maxHeap.pop();
}
/* 访问堆顶元素 */
function peekMinHeap(maxHeap) {
// 元素取反
return -maxHeap.peek();
}
/* 取出堆中元素 */
function getMinHeap(maxHeap) {
// 元素取反
return maxHeap.getMaxHeap().map((num) => -num);
}
/* 基于堆查找数组中最大的 k 个元素 */
function topKHeap(nums, k) {
// 初始化小顶堆
// 请注意：我们将堆中所有元素取反，从而用大顶堆来模拟小顶堆
const maxHeap = new MaxHeap([]);
// 将数组的前 k 个元素入堆
for (let i = 0; i < k; i++) {
pushMinHeap(maxHeap, nums[i]);
}
// 从第 k+1 个元素开始，保持堆的长度为 k
for (let i = k; i < nums.length; i++) {
// 若当前元素大于堆顶元素，则将堆顶元素出堆、当前元素入堆
if (nums[i] > peekMinHeap(maxHeap)) {
popMinHeap(maxHeap);
pushMinHeap(maxHeap, nums[i]);
}
}
// 返回堆中元素
return getMinHeap(maxHeap);
}
整个过程总共执行了 N 轮入堆和出堆，堆的最大长度为 K ，因此时间复杂度为 O（n log k） 。
该方法的效率很高，当 k 较小时，时间复杂度趋向 O(n)；当 k 较大时，不会超过 O(n log n) 。
当有数据不断加入，它可以持续维护堆内的元素，从而实现最大的 k 个元素的动态更新。
其他应用
- 优先队列：堆通常作为实现优先队列的首选数据结构，其入队和出队操作的时间复杂度均为 O(log n) ，而建堆操作为 O(n) ，都非常高效。
- 堆排序：给定一组数据，我们可以用它们建立一个堆，然后不断地执行元素出堆操作，从而得到有序数据。
小结
本篇文章，我们介绍了使用堆实现Top-K的原理，这是一种经典方式，但不是唯一方式。根据具体场景和数据特点，也可以选择其他方案。比如：快速选择、计数排序/桶排序等。
这就是工程实践中的经典权衡，理论复杂度只是起点，实际选择需要考虑内存、实时性、数据特性、系统架构等综合因素。
送“书”活动来啦！
之前总有人问《JavaScript高级程序设计》（第5版）有电子版吗？现在有啦！
参与方式(“前端说书匠”公众号内参与)：
1、点个小❤ + 转发朋友圈
2、分享你2026年的学习计划或者你想要看到解读的书籍/知识点
1、2须同时满足，最终取评论点赞数前三，若有并列，以时间为序
如有特别优质的，可获额外奖励，此条解释权归“说书匠”所有。
开始时间：2026年2月2日早9:00，本篇文章发布后
截止时间：2026年2月6日晚23:00
