每个系列一本前端好书，帮你轻松学重点。

本系列来自上海交通大学硕士，华为高级算法工程师 靳宇栋 的 《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的最佳方案？

原理如下：

1. 初始化一个小顶堆，其堆顶元素最小。
2. 将前 k 个元素依次入堆。
3. 从第 k + 1 个元素开始，若当前元素大于堆顶元素，则将堆顶元素出堆，并将当前元素入堆。
4. 遍历完成后，堆中保存的就是最大的 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，通过它来定位“左、右、父”节点。这里只关心位置和索引，跟值无关。

当堆结构形成后，就可以进行相关操作了。

主要关注：入堆和出堆。

因为它们可能打破堆结构已经形成的平衡，要做出调整来重新获得平衡。

入堆

关键步骤：

1. 将新元素添加至堆底，即数组中新增一个元素；
2. 新增元素可能小于堆顶的元素，也可能大于，小的时候不用动，如果大，则需要自底向上一路比较，这个操作称作“堆化”。
3. 堆化的过程就是在做逐层比较和交换，直至越过根节点或遇到无须交换的节点，结束。

/* 元素入堆 */
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;
    }
}

入堆这么麻烦，出堆是不是就容易了，直接删掉？

当然不是，堆中的元素都存在着相互关联，直接删掉带来的结果是，其余所有元素都要发生变化，这不是明智的做法。

出堆操作也分为以下几步：

1. 交换堆顶元素与堆底元素（根节点与最右叶节点）。
2. 将堆底元素从列表中删除（注意，由于已经交换，因此实际上删除的是原来的堆顶元素）。
3. 从根节点开始，从顶至底执行堆化。

/* 元素出堆 */
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