上周帮一位准备跳槽的前端朋友做模拟面试我出了一道很常见的题“实现一个结构支持插入数据并且能以 O(log n) 的代价取出当前最小值。”他脱口而出“那我先放数组里取的时候 sort 一下不就行了”这个回答不算错但暴露了一个典型问题。sort 一次确实是 O(n log n)可面试官真正想听的是用堆实现的优先队列插入和取最值都是 O(log n)。一旦问到这第一反应是 sort 的人基本就露馅了。这篇文章就是写给和当时的他一样面试怕手撕堆数据结构的同学。我会把堆的原理、手写代码、面试套路一次讲清楚最后再给出一套可以直接用的实战技巧。内容不涉及高深数学只要你写过数组就能跟得上。1. 面试现场写出“四不像”之后我才明白堆到底该怎么学1.1 那个让我当场红温的瞬间当时我让模拟面试的朋友进一步优化他想了半天写出了一个“伪堆”数组里维护一个 min 变量每次插入都比一下取最小值 O(1)但插入……他写到一半自己停住了。因为一旦执行了一次 popmin 就失效了又得重新遍历找最小值。这就是对“堆”没有结构认知的典型表现知道名字知道大概思路但代码落不了地。后来我陪他把堆从头推了一遍二十分钟后他自己写出了 TopK。他在感叹“原来这么简单”的时候我突然意识到堆这个数据结构对前端来说不是学不会而是缺少一个“用数组连续存储 上浮下沉”的思维锚点。你抓住这两个词堆的一大半东西就通了。1.2 先把概念厘清算法堆不等于内存堆在聊数据结构之前我建议先做一个名词澄清。浏览器引擎的堆heap是内存划分的一个区域用来存对象和闭包变量而你说的“堆排序”“堆空间不足”是完全不同的概念。很多文章和热搜里经常把两者混在一起导致不少人被“堆”这个字劝退。面试时如果面试官说“堆”指的是数据结构里那棵完全二叉树。你要做的是快速在脑内切换语境别一听到堆就去想 V8 内存那会把自己绕进去。数据结构里的堆本质就是一棵有秩序的树内存里的堆本质是一块地。重名但完全是两码事。1.3 前端业务里堆真的有用吗有而且不少。说几个我亲身见过的场景直播间的实时热度榜用户点赞不断产生系统只需要把热度前 50 的直播间推送出来。如果每来一个数据就全量排序一次每次 O(n log n)数据量一大就扛不住用一个容量为 50 的小顶堆每次 O(log 50)几乎可以忽略不计。前端埋点上报时错误日志的优先级通常高于普通 PV 日志这是一个典型的优先队列场景而优先队列最常见的实现就是堆。React 的 Scheduler 调度器内部就有一份最小堆实现通过它管理“谁该在下一个时间片继续执行”。你能在面试里说出“React 源码里的任务调度用了堆”面试官对你的评价会完全不同。所以“前端学堆没用”这句话至少从面试和真实工程两个维度看都不成立。2. 用数组种树堆的存储结构和四个核心动作2.1 关键词一完全二叉树严格定义可以很绕但你可以通俗理解成一棵二叉树每一层都从左到右排满只有最后一层允许右边缺几个节点。这种“紧凑从左往右排”的形态是堆能用数组存储的前提。它带来的最大便利是你不需要用 Node 和指针去建树一个普通的数组就够了。数组下标和树的关系有三条公式面试前背下来就行下标 i 的左右子节点是2 * i 1和2 * i 2下标 i 的父节点是Math.floor((i - 1) / 2)最后一个非叶节点是Math.floor(length / 2) - 1我解释概念时很喜欢举一个具体例子数组[4, 10, 3, 5, 1]下标 0 的 4 是根下标 1 和 2 分别是它的左右子下标 3 和 4 是下标 1 的孩子。这棵树一共 5 个节点形状紧凑逻辑上是一棵完全二叉树。2.2 关键词二堆序光有数组下标公式还不够堆还有一个“序”的约束大顶堆每个父节点 左右子节点堆顶是最大值小顶堆每个父节点 左右子节点堆顶是最小值注意只有父子之间有这种大小关系兄弟之间没有任何约定。比如小顶堆里左子比右子大是完全正常的。用公司来类比CEO堆顶一定最强但两个部门 leader左右子谁强谁弱不影响大局。这也是堆和二叉搜索树的核心区别之一——二叉搜索树要求左 根 右堆只要求“上下有序左右随意”。2.3 四个核心动作上浮、下沉、插入、取顶有了存储结构和堆序堆的操作其实就几句话插入 push新元素放到数组末尾然后一路“上浮”到合适位置取堆顶并删除 pop把堆顶和末尾元素互换弹出末尾然后让新堆顶“下沉”到合适位置偷看堆顶 peek直接拿data[0]批量建堆 heapify从最后一个非叶节点开始从右往左、从下往上逐个下沉下面是一个完整可用的最小堆类。这版已经预留了 compare 参数数字场景下可以忽略它先按数字理解就好比较器的用途我放到第 5 章单独拆开讲。class MinHeap { constructor(compareFn) { this.data []; this.compare compareFn || ((a, b) a - b); } size() { return this.data.length; } peek() { return this.data.length ? this.data[0] : undefined; } swap(i, j) { [this.data[i], this.data[j]] [this.data[j], this.data[i]]; } push(val) { this.data.push(val); this._siftUp(this.data.length - 1); } _siftUp(i) { while (i 0) { const parent Math.floor((i - 1) / 2); if (this.compare(this.data[i], this.data[parent]) 0) break; this.swap(i, parent); i parent; } } pop() { if (this.data.length 0) return undefined; if (this.data.length 1) return this.data.pop(); const top this.data[0]; this.data[0] this.data.pop(); this._siftDown(0); return top; } _siftDown(i) { const n this.data.length; while (true) { let target i; const left 2 * i 1; const right 2 * i 2; if (left n this.compare(this.data[left], this.data[target]) 0) target left; if (right n this.compare(this.data[right], this.data[target]) 0) target right; if (target i) break; this.swap(i, target); i target; } } }说三个细节。第一下沉和上浮建议用循环而不是递归。虽然树的高度是 log n递归不会爆栈但手写时 while 循环的终止条件更直观调试也更快。第二交换用解构一行写完省得写临时变量减少出错概率。第三等值元素时用 0直接 break不要继续交换否则可能死循环这个问题我在第 6 章还会重点提。有了这个类一个最小堆的“增、删、查”就齐了。剩下的问题就是用它去解面试题。3. 复杂度这本账堆为什么能成为“TopK 专业户”3.1 一张表看清堆的家底面试手撕算法复杂度是必问环节。堆的复杂度非常固定我整理成了一张表操作时间复杂度说明peekO(1)直接取数组第一个元素pushO(log n)末尾插入后上浮popO(log n)堆顶与末尾交换后下沉批量建堆O(n)从最后一个非叶节点倒着下沉堆排序O(n log n)建堆 O(n) 弹出 n 次 O(log n)为什么 push 和 pop 是 O(log n)因为完全二叉树的高度是 log2 n上浮或下沉每次走一条从某个节点到根或叶的路径最多 log n 步。3.2 为什么批量建堆不是 O(n log n)这个点非常容易被追问。直觉解释是完全二叉树里靠近叶子的节点数量最多但它们下沉的距离很短很多节点只需要下沉 0 次或 1 次靠近根的节点虽然要下沉很多步但数量少。加权下来总的操作次数是收敛的趋近于 2n所以是 O(n)。反过来如果你用循环一个个 push 建堆每个元素都要从最底部开始上浮那就是 O(n log n)。所以面试里如果给你一个现成数组让你建堆你应该下意识想到“批量 heapify”这条更优路径而不是无脑 for 循环 push。这也是区分“背过堆排序”和“真懂堆”的好问题。3.3 堆、全量排序、快速选择到底选谁前端最容易理解的 TopK 场景从一百万个数字里找出前 100 大的。三种思路对比一下全量排序O(n log n)简单粗暴适合数据量不大或者之后要反复查全榜的情况。堆O(n log k)这里 k100基本可以看成 O(n)适合“只关心前 k 个”或者数据是不断流入的。快速选择平均 O(n)但只适合找第 k 大这一个固定值数据必须整体在内存里没法处理流式数据。结论需求越“局部”、数据越“流式”堆的优势越明显。这跟前端埋点、日志告警这类实时数据处理场景天然匹配。很多人觉得算法离业务远其实是没选对工具。3.4 面试听到这些词先想堆面试高频词里只要出现“Top k”“第 k 大/小”“合并有序序列”“数据流中位数”“最近到期任务”都可以优先往堆上想。如果只是“要一个值、数据已经在内存里”再考虑快速选择。这个判断习惯能帮你快速锁定解法不至于在现场反复换方向。4. 高频手撕题的三板斧TopK、多路归并、中位数4.1 TopK小顶堆守门槛先讲最经典的题目给定一个数组找出前 K 个最大的元素。思路就一句话维护一个容量为 K 的小顶堆堆顶是这 K 个元素里最小的那个也就是“门槛”。遍历数组时如果元素比门槛大就把它和门槛交换如果比门槛小直接跳过。最终堆里剩下的就是前 K 大。记忆口诀求前 K 大用小顶堆。堆顶就是守门员比你强的人才够资格进来。function topK(nums, k) { const heap new MinHeap(); for (const num of nums) { if (heap.size() k) { heap.push(num); } else if (num heap.peek()) { heap.pop(); heap.push(num); } } return heap.data; }这里有个非常反直觉的点求最大的前 K 个反而用小顶堆。原因是小顶堆能 O(1) 拿到当前 K 个候选里的最小值也就是“最差的那个”。新来的数字只要比它强就顶替它。要注意heap.data里的元素满足堆序但不是严格排序。如果题目要求降序输出可以把堆里元素挨个 pop 出来再反转。这个细节说出口面试官会觉得你懂边界。前 K 小就是完全对称用大顶堆堆顶是“天花板”新来数字比它小才顶替它。很多同学在这里绕晕我的记忆方法是凡是“淘汰最差”的题都用小根堆凡是“淘汰最好”的题都用大根堆。4.2 合并K个有序链表多路归并第二个高频题是合并 K 个有序链表。朴素做法是每轮遍历 K 个链表头找最小值总复杂度 O(NK)其中 N 是节点总数。用堆就能把找最小值的过程优化到 O(log K)整体复杂度变成 O(N log K)。做法很像多路归并先把每个链表的头节点放进一个小顶堆堆顶就是当前所有链表里最小的节点弹出它之后把它所在链表的下一个节点补进堆重复这个过程直到堆空。function mergeKLists(lists) { // 堆里存的是链表节点比较器比较 val const heap new MinHeap((a, b) a.val - b.val); for (const head of lists) { if (head) heap.push(head); } const dummy { val: 0, next: null }; let tail dummy; while (heap.size() 0) { const node heap.pop(); tail.next node; tail node; if (node.next) heap.push(node.next); } return dummy.next; }这段代码最大的亮点是堆里存的不再是数字而是链表节点。你可能已经注意到这个堆类因为有 compare 参数所以能直接支持对象比较。这正是我在第 2 章预留 compare 参数的原因。4.3 数据流中位数两根堆左右互搏第三个经典题数据流中位数。数据不是一次性给全而是不断流进来要求随时能返回当前所有数据的中位数。思路是维护两个堆左边一个大顶堆存较小的一半右边一个小顶堆存较大的一半。两个堆始终保持“左边数量不超过右边 1 个”。这样一来中位数要么是左堆顶要么是左右堆顶的平均值。由于我们目前只有 MinHeap可以用“取负”技巧模拟大顶堆往左堆存-num那么左堆堆顶的相反数就是左半边最大值。下面是完整实现class MedianFinder { constructor() { // left 用最小堆存负数模拟最大堆right 是普通最小堆 this.left new MinHeap(); this.right new MinHeap(); } addNum(num) { if (this.left.size() 0 || num -this.left.peek()) { this.left.push(-num); } else { this.right.push(num); } // 保持 left.size() 等于 right.size() 或比 right 多 1 if (this.left.size() this.right.size() 1) { this.right.push(-this.left.pop()); } if (this.right.size() this.left.size()) { this.left.push(-this.right.pop()); } } findMedian() { if (this.left.size() this.right.size()) return -this.left.peek(); return (-this.left.peek() this.right.peek()) / 2; } }验证一下输入 5、3、10。插 5 时左堆存 -5中位数就是 5。插 3 时 3 比 5 小进左堆左堆变成 5 和 3堆顶是 -5超出一个把 -5 弹给右堆右堆存 5此时左堆 -3右堆 5中位数为 (3 5) / 2 4。插 10 时 10 比 3 大进右堆右堆变成 5、10比左堆多把 5 弹回左堆最终左堆是 3、5右堆是 10中位数是 5。结果正确。这个“取负模拟大顶堆”的技巧在笔试里非常实用省得再写一个 MaxHeap 类。但可读性差一些如果你有富余时间推荐把大顶堆写完整代码会更直白。4.4 堆排序考到就是送分题堆排序严格来说不算独立题型但它经常作为“附加题”出现。比如面试官会问“既然你会堆那原地堆排序会写吗”堆排序的核心就两步先把数组原地建成大顶堆然后反复把堆顶和末尾未排序区交换交换后让新堆顶下沉。这里有一个容易说反的点大顶堆排序出来是升序。function heapSort(nums) { const n nums.length; const swap (i, j) { [nums[i], nums[j]] [nums[j], nums[i]]; }; const siftDown (i, size) { while (true) { let largest i; const left 2 * i 1; const right 2 * i 2; if (left size nums[left] nums[largest]) largest left; if (right size nums[right] nums[largest]) largest right; if (largest i) break; swap(i, largest); i largest; } }; // 1. 从最后一个非叶节点开始批量建大顶堆 for (let i Math.floor(n / 2) - 1; i 0; i--) { siftDown(i, n); } // 2. 逐个把堆顶放到数组末尾 for (let i n - 1; i 0; i--) { swap(0, i); siftDown(0, i); } return nums; }面试中提到堆排序要主动说清楚两件事时间 O(n log n)空间 O(1)但它是不稳定排序。如果你先讲一遍“堆排序不稳定、为什么不稳定”面试官通常会很满意。5. 从“数字专用”到“万物可堆”比较器的设计与通用化改造5.1 一个坑JS 的 sort 默认不是数字排序先看一个前端老生常谈的坑[10, 9, 80].sort()输出的不是[9, 10, 80]而是[10, 80, 9]。原因是数组默认按字符串字典序排序而不是按数字大小。堆也一样。如果不传比较器它就只认识能直接做减法的数字。可真实业务里我们要排的往往是对象。比如直播间热度榜堆里存的是{ score: 90, nickname: xiaoming }你要按 score 排序。这时就必须让堆知道“拿对象的哪个字段比大小”。5.2 compare 的正负约定我在第 2 章的 MinHeap 里预留的 compare遵循和原生 sort 一致的约定compare(a, b)返回负数表示 a 应该排在 b 前面离堆顶更近返回正数表示 a 应该排在 b 后面返回 0表示两者相等默认的(a, b) a - b就是数字升序的小顶堆。如果改成(a, b) b - a整个堆就会翻转成大顶堆。有了这个约定堆就能装任何东西// 直播间热度榜按分数降序找前 10 名 const hotHeap new MinHeap((a, b) b.score - a.score); // 任务调度按截止时间升序最先到期的在最上面 const taskHeap new MinHeap((a, b) a.deadline - b.deadline);5.3 改造差异其实只有三处对比第 2 章的代码支持比较器之后核心改动就三处构造函数存一份 compare上浮时比较新元素和父节点用compare(...) 0作为终止条件下沉时用compare(left, target) 0和compare(right, target) 0选择下沉方向你可以把第 2 章的代码拿出来自己改一遍改完你就能跟别人说“我封装过支持比较器的通用堆。”这比背十道题都有用。5.4 堆不止能解题还是优先队列的骨架抽象一步看堆就是优先队列最常见的实现。任何“每次都要取当前最值”的诉求都可以尝试用堆。前端埋点里的错误日志优先上报、定时器按到期时间管理、实时看板只保留 TopN本质上都是同一个模型。当你能把一道算法题抽象成“维护一个动态集合的最值”堆自然就成了选项。这个时候你不只是在背题而是在用工具解决问题。6. 手撕现场稳住不翻车边界、用例与节奏控制6.1 边界条件清单代码写对一半靠逻辑另一半靠边界。我整理了一份现场自查清单空堆调用 pop 怎么办返回 undefined不能抛异常。堆里只有一个元素时 pop 怎么办直接return this.data.pop()避免先赋值再 pop 造成“自己换自己”的混乱。出现重复值怎么办上浮和下沉的判断要用 0或 0及时 break不要让两个相等元素互相交换。我用[7, 7, 7]验证过多版代码相等处理不对会死循环。6.2 三组自测用例面试写完之后不要急着说“写完了”先用三组用例在脑子里跑一遍空数组pop 返回 undefinedpush 一个元素后 peek 能拿到它。单元素数组[1]建堆、push、pop 都正常。普通数组[3, 1, 4, 1, 5, 9, 2, 6]找前 3 大结果应为 5、6、9顺序可以不同这个过程 30 秒能推完。平时练习可以在浏览器控制台直接跑不需要搭环境。前端人练算法最大的优势就是打开 DevTools 就能验证。6.3 面试中最容易说错的几句话有些说法一出口面试官就知道你是背题还是真懂。我列几个反面例子“堆排序和 sort 差不多”差很多。堆排序不稳定原地空间 O(1)原生 sort 在不同引擎里可能是稳定的归并插入排序。“堆是一棵用链表表示的树”这是最常见的误区。堆的核心是数组连续存储用下标计算父子关系这也是它比普通二叉树更省空间的原因。“堆就是优先队列”严格说优先队列是抽象概念堆是它的常见实现。这样说显得专业得多。6.4 复习节奏建议如果你从零开始准备我建议按下面顺序连续练一周第一天开始每天默写一遍最小堆类目标 5 分钟写完。第二天开始练 TopK 和堆排序。最后练合并 K 个有序链表和数据流中位数因为它们依赖比较器和双堆思维。不要背代码每次写之前先画一遍上浮下沉的路径图。画到第三四天你会发现手写堆从“背诵”变成了“推导”这个过程比结果重要得多。最后分享一个我自己的经验。我第一次手写堆时总想“把这个下沉函数写对再写下一个”结果一步错步步错。后来我改成先画一棵三层小树把插入、删除的路径标出来再对着图写代码正确率提高了很多。另一个习惯是面试开始时先跟面试官确认清楚“数组是静态的还是流式的K 可能等于 n 吗要升序还是降序”这三个问题一确认代码怎么写基本就定了。祝各位前端同学下次手撕堆不是紧张而是兴奋。
上周帮一位准备跳槽的前端朋友做模拟面试我出了一道很常见的题“实现一个结构支持插入数据并且能以 O(log n) 的代价取出当前最小值。”他脱口而出“那我先放数组里取的时候 sort 一下不就行了”这个回答不算错但暴露了一个典型问题。sort 一次确实是 O(n log n)可面试官真正想听的是用堆实现的优先队列插入和取最值都是 O(log n)。一旦问到这第一反应是 sort 的人基本就露馅了。这篇文章就是写给和当时的他一样面试怕手撕堆数据结构的同学。我会把堆的原理、手写代码、面试套路一次讲清楚最后再给出一套可以直接用的实战技巧。内容不涉及高深数学只要你写过数组就能跟得上。1. 面试现场写出“四不像”之后我才明白堆到底该怎么学1.1 那个让我当场红温的瞬间当时我让模拟面试的朋友进一步优化他想了半天写出了一个“伪堆”数组里维护一个 min 变量每次插入都比一下取最小值 O(1)但插入……他写到一半自己停住了。因为一旦执行了一次 popmin 就失效了又得重新遍历找最小值。这就是对“堆”没有结构认知的典型表现知道名字知道大概思路但代码落不了地。后来我陪他把堆从头推了一遍二十分钟后他自己写出了 TopK。他在感叹“原来这么简单”的时候我突然意识到堆这个数据结构对前端来说不是学不会而是缺少一个“用数组连续存储 上浮下沉”的思维锚点。你抓住这两个词堆的一大半东西就通了。1.2 先把概念厘清算法堆不等于内存堆在聊数据结构之前我建议先做一个名词澄清。浏览器引擎的堆heap是内存划分的一个区域用来存对象和闭包变量而你说的“堆排序”“堆空间不足”是完全不同的概念。很多文章和热搜里经常把两者混在一起导致不少人被“堆”这个字劝退。面试时如果面试官说“堆”指的是数据结构里那棵完全二叉树。你要做的是快速在脑内切换语境别一听到堆就去想 V8 内存那会把自己绕进去。数据结构里的堆本质就是一棵有秩序的树内存里的堆本质是一块地。重名但完全是两码事。1.3 前端业务里堆真的有用吗有而且不少。说几个我亲身见过的场景直播间的实时热度榜用户点赞不断产生系统只需要把热度前 50 的直播间推送出来。如果每来一个数据就全量排序一次每次 O(n log n)数据量一大就扛不住用一个容量为 50 的小顶堆每次 O(log 50)几乎可以忽略不计。前端埋点上报时错误日志的优先级通常高于普通 PV 日志这是一个典型的优先队列场景而优先队列最常见的实现就是堆。React 的 Scheduler 调度器内部就有一份最小堆实现通过它管理“谁该在下一个时间片继续执行”。你能在面试里说出“React 源码里的任务调度用了堆”面试官对你的评价会完全不同。所以“前端学堆没用”这句话至少从面试和真实工程两个维度看都不成立。2. 用数组种树堆的存储结构和四个核心动作2.1 关键词一完全二叉树严格定义可以很绕但你可以通俗理解成一棵二叉树每一层都从左到右排满只有最后一层允许右边缺几个节点。这种“紧凑从左往右排”的形态是堆能用数组存储的前提。它带来的最大便利是你不需要用 Node 和指针去建树一个普通的数组就够了。数组下标和树的关系有三条公式面试前背下来就行下标 i 的左右子节点是2 * i 1和2 * i 2下标 i 的父节点是Math.floor((i - 1) / 2)最后一个非叶节点是Math.floor(length / 2) - 1我解释概念时很喜欢举一个具体例子数组[4, 10, 3, 5, 1]下标 0 的 4 是根下标 1 和 2 分别是它的左右子下标 3 和 4 是下标 1 的孩子。这棵树一共 5 个节点形状紧凑逻辑上是一棵完全二叉树。2.2 关键词二堆序光有数组下标公式还不够堆还有一个“序”的约束大顶堆每个父节点 左右子节点堆顶是最大值小顶堆每个父节点 左右子节点堆顶是最小值注意只有父子之间有这种大小关系兄弟之间没有任何约定。比如小顶堆里左子比右子大是完全正常的。用公司来类比CEO堆顶一定最强但两个部门 leader左右子谁强谁弱不影响大局。这也是堆和二叉搜索树的核心区别之一——二叉搜索树要求左 根 右堆只要求“上下有序左右随意”。2.3 四个核心动作上浮、下沉、插入、取顶有了存储结构和堆序堆的操作其实就几句话插入 push新元素放到数组末尾然后一路“上浮”到合适位置取堆顶并删除 pop把堆顶和末尾元素互换弹出末尾然后让新堆顶“下沉”到合适位置偷看堆顶 peek直接拿data[0]批量建堆 heapify从最后一个非叶节点开始从右往左、从下往上逐个下沉下面是一个完整可用的最小堆类。这版已经预留了 compare 参数数字场景下可以忽略它先按数字理解就好比较器的用途我放到第 5 章单独拆开讲。class MinHeap { constructor(compareFn) { this.data []; this.compare compareFn || ((a, b) a - b); } size() { return this.data.length; } peek() { return this.data.length ? this.data[0] : undefined; } swap(i, j) { [this.data[i], this.data[j]] [this.data[j], this.data[i]]; } push(val) { this.data.push(val); this._siftUp(this.data.length - 1); } _siftUp(i) { while (i 0) { const parent Math.floor((i - 1) / 2); if (this.compare(this.data[i], this.data[parent]) 0) break; this.swap(i, parent); i parent; } } pop() { if (this.data.length 0) return undefined; if (this.data.length 1) return this.data.pop(); const top this.data[0]; this.data[0] this.data.pop(); this._siftDown(0); return top; } _siftDown(i) { const n this.data.length; while (true) { let target i; const left 2 * i 1; const right 2 * i 2; if (left n this.compare(this.data[left], this.data[target]) 0) target left; if (right n this.compare(this.data[right], this.data[target]) 0) target right; if (target i) break; this.swap(i, target); i target; } } }说三个细节。第一下沉和上浮建议用循环而不是递归。虽然树的高度是 log n递归不会爆栈但手写时 while 循环的终止条件更直观调试也更快。第二交换用解构一行写完省得写临时变量减少出错概率。第三等值元素时用 0直接 break不要继续交换否则可能死循环这个问题我在第 6 章还会重点提。有了这个类一个最小堆的“增、删、查”就齐了。剩下的问题就是用它去解面试题。3. 复杂度这本账堆为什么能成为“TopK 专业户”3.1 一张表看清堆的家底面试手撕算法复杂度是必问环节。堆的复杂度非常固定我整理成了一张表操作时间复杂度说明peekO(1)直接取数组第一个元素pushO(log n)末尾插入后上浮popO(log n)堆顶与末尾交换后下沉批量建堆O(n)从最后一个非叶节点倒着下沉堆排序O(n log n)建堆 O(n) 弹出 n 次 O(log n)为什么 push 和 pop 是 O(log n)因为完全二叉树的高度是 log2 n上浮或下沉每次走一条从某个节点到根或叶的路径最多 log n 步。3.2 为什么批量建堆不是 O(n log n)这个点非常容易被追问。直觉解释是完全二叉树里靠近叶子的节点数量最多但它们下沉的距离很短很多节点只需要下沉 0 次或 1 次靠近根的节点虽然要下沉很多步但数量少。加权下来总的操作次数是收敛的趋近于 2n所以是 O(n)。反过来如果你用循环一个个 push 建堆每个元素都要从最底部开始上浮那就是 O(n log n)。所以面试里如果给你一个现成数组让你建堆你应该下意识想到“批量 heapify”这条更优路径而不是无脑 for 循环 push。这也是区分“背过堆排序”和“真懂堆”的好问题。3.3 堆、全量排序、快速选择到底选谁前端最容易理解的 TopK 场景从一百万个数字里找出前 100 大的。三种思路对比一下全量排序O(n log n)简单粗暴适合数据量不大或者之后要反复查全榜的情况。堆O(n log k)这里 k100基本可以看成 O(n)适合“只关心前 k 个”或者数据是不断流入的。快速选择平均 O(n)但只适合找第 k 大这一个固定值数据必须整体在内存里没法处理流式数据。结论需求越“局部”、数据越“流式”堆的优势越明显。这跟前端埋点、日志告警这类实时数据处理场景天然匹配。很多人觉得算法离业务远其实是没选对工具。3.4 面试听到这些词先想堆面试高频词里只要出现“Top k”“第 k 大/小”“合并有序序列”“数据流中位数”“最近到期任务”都可以优先往堆上想。如果只是“要一个值、数据已经在内存里”再考虑快速选择。这个判断习惯能帮你快速锁定解法不至于在现场反复换方向。4. 高频手撕题的三板斧TopK、多路归并、中位数4.1 TopK小顶堆守门槛先讲最经典的题目给定一个数组找出前 K 个最大的元素。思路就一句话维护一个容量为 K 的小顶堆堆顶是这 K 个元素里最小的那个也就是“门槛”。遍历数组时如果元素比门槛大就把它和门槛交换如果比门槛小直接跳过。最终堆里剩下的就是前 K 大。记忆口诀求前 K 大用小顶堆。堆顶就是守门员比你强的人才够资格进来。function topK(nums, k) { const heap new MinHeap(); for (const num of nums) { if (heap.size() k) { heap.push(num); } else if (num heap.peek()) { heap.pop(); heap.push(num); } } return heap.data; }这里有个非常反直觉的点求最大的前 K 个反而用小顶堆。原因是小顶堆能 O(1) 拿到当前 K 个候选里的最小值也就是“最差的那个”。新来的数字只要比它强就顶替它。要注意heap.data里的元素满足堆序但不是严格排序。如果题目要求降序输出可以把堆里元素挨个 pop 出来再反转。这个细节说出口面试官会觉得你懂边界。前 K 小就是完全对称用大顶堆堆顶是“天花板”新来数字比它小才顶替它。很多同学在这里绕晕我的记忆方法是凡是“淘汰最差”的题都用小根堆凡是“淘汰最好”的题都用大根堆。4.2 合并K个有序链表多路归并第二个高频题是合并 K 个有序链表。朴素做法是每轮遍历 K 个链表头找最小值总复杂度 O(NK)其中 N 是节点总数。用堆就能把找最小值的过程优化到 O(log K)整体复杂度变成 O(N log K)。做法很像多路归并先把每个链表的头节点放进一个小顶堆堆顶就是当前所有链表里最小的节点弹出它之后把它所在链表的下一个节点补进堆重复这个过程直到堆空。function mergeKLists(lists) { // 堆里存的是链表节点比较器比较 val const heap new MinHeap((a, b) a.val - b.val); for (const head of lists) { if (head) heap.push(head); } const dummy { val: 0, next: null }; let tail dummy; while (heap.size() 0) { const node heap.pop(); tail.next node; tail node; if (node.next) heap.push(node.next); } return dummy.next; }这段代码最大的亮点是堆里存的不再是数字而是链表节点。你可能已经注意到这个堆类因为有 compare 参数所以能直接支持对象比较。这正是我在第 2 章预留 compare 参数的原因。4.3 数据流中位数两根堆左右互搏第三个经典题数据流中位数。数据不是一次性给全而是不断流进来要求随时能返回当前所有数据的中位数。思路是维护两个堆左边一个大顶堆存较小的一半右边一个小顶堆存较大的一半。两个堆始终保持“左边数量不超过右边 1 个”。这样一来中位数要么是左堆顶要么是左右堆顶的平均值。由于我们目前只有 MinHeap可以用“取负”技巧模拟大顶堆往左堆存-num那么左堆堆顶的相反数就是左半边最大值。下面是完整实现class MedianFinder { constructor() { // left 用最小堆存负数模拟最大堆right 是普通最小堆 this.left new MinHeap(); this.right new MinHeap(); } addNum(num) { if (this.left.size() 0 || num -this.left.peek()) { this.left.push(-num); } else { this.right.push(num); } // 保持 left.size() 等于 right.size() 或比 right 多 1 if (this.left.size() this.right.size() 1) { this.right.push(-this.left.pop()); } if (this.right.size() this.left.size()) { this.left.push(-this.right.pop()); } } findMedian() { if (this.left.size() this.right.size()) return -this.left.peek(); return (-this.left.peek() this.right.peek()) / 2; } }验证一下输入 5、3、10。插 5 时左堆存 -5中位数就是 5。插 3 时 3 比 5 小进左堆左堆变成 5 和 3堆顶是 -5超出一个把 -5 弹给右堆右堆存 5此时左堆 -3右堆 5中位数为 (3 5) / 2 4。插 10 时 10 比 3 大进右堆右堆变成 5、10比左堆多把 5 弹回左堆最终左堆是 3、5右堆是 10中位数是 5。结果正确。这个“取负模拟大顶堆”的技巧在笔试里非常实用省得再写一个 MaxHeap 类。但可读性差一些如果你有富余时间推荐把大顶堆写完整代码会更直白。4.4 堆排序考到就是送分题堆排序严格来说不算独立题型但它经常作为“附加题”出现。比如面试官会问“既然你会堆那原地堆排序会写吗”堆排序的核心就两步先把数组原地建成大顶堆然后反复把堆顶和末尾未排序区交换交换后让新堆顶下沉。这里有一个容易说反的点大顶堆排序出来是升序。function heapSort(nums) { const n nums.length; const swap (i, j) { [nums[i], nums[j]] [nums[j], nums[i]]; }; const siftDown (i, size) { while (true) { let largest i; const left 2 * i 1; const right 2 * i 2; if (left size nums[left] nums[largest]) largest left; if (right size nums[right] nums[largest]) largest right; if (largest i) break; swap(i, largest); i largest; } }; // 1. 从最后一个非叶节点开始批量建大顶堆 for (let i Math.floor(n / 2) - 1; i 0; i--) { siftDown(i, n); } // 2. 逐个把堆顶放到数组末尾 for (let i n - 1; i 0; i--) { swap(0, i); siftDown(0, i); } return nums; }面试中提到堆排序要主动说清楚两件事时间 O(n log n)空间 O(1)但它是不稳定排序。如果你先讲一遍“堆排序不稳定、为什么不稳定”面试官通常会很满意。5. 从“数字专用”到“万物可堆”比较器的设计与通用化改造5.1 一个坑JS 的 sort 默认不是数字排序先看一个前端老生常谈的坑[10, 9, 80].sort()输出的不是[9, 10, 80]而是[10, 80, 9]。原因是数组默认按字符串字典序排序而不是按数字大小。堆也一样。如果不传比较器它就只认识能直接做减法的数字。可真实业务里我们要排的往往是对象。比如直播间热度榜堆里存的是{ score: 90, nickname: xiaoming }你要按 score 排序。这时就必须让堆知道“拿对象的哪个字段比大小”。5.2 compare 的正负约定我在第 2 章的 MinHeap 里预留的 compare遵循和原生 sort 一致的约定compare(a, b)返回负数表示 a 应该排在 b 前面离堆顶更近返回正数表示 a 应该排在 b 后面返回 0表示两者相等默认的(a, b) a - b就是数字升序的小顶堆。如果改成(a, b) b - a整个堆就会翻转成大顶堆。有了这个约定堆就能装任何东西// 直播间热度榜按分数降序找前 10 名 const hotHeap new MinHeap((a, b) b.score - a.score); // 任务调度按截止时间升序最先到期的在最上面 const taskHeap new MinHeap((a, b) a.deadline - b.deadline);5.3 改造差异其实只有三处对比第 2 章的代码支持比较器之后核心改动就三处构造函数存一份 compare上浮时比较新元素和父节点用compare(...) 0作为终止条件下沉时用compare(left, target) 0和compare(right, target) 0选择下沉方向你可以把第 2 章的代码拿出来自己改一遍改完你就能跟别人说“我封装过支持比较器的通用堆。”这比背十道题都有用。5.4 堆不止能解题还是优先队列的骨架抽象一步看堆就是优先队列最常见的实现。任何“每次都要取当前最值”的诉求都可以尝试用堆。前端埋点里的错误日志优先上报、定时器按到期时间管理、实时看板只保留 TopN本质上都是同一个模型。当你能把一道算法题抽象成“维护一个动态集合的最值”堆自然就成了选项。这个时候你不只是在背题而是在用工具解决问题。6. 手撕现场稳住不翻车边界、用例与节奏控制6.1 边界条件清单代码写对一半靠逻辑另一半靠边界。我整理了一份现场自查清单空堆调用 pop 怎么办返回 undefined不能抛异常。堆里只有一个元素时 pop 怎么办直接return this.data.pop()避免先赋值再 pop 造成“自己换自己”的混乱。出现重复值怎么办上浮和下沉的判断要用 0或 0及时 break不要让两个相等元素互相交换。我用[7, 7, 7]验证过多版代码相等处理不对会死循环。6.2 三组自测用例面试写完之后不要急着说“写完了”先用三组用例在脑子里跑一遍空数组pop 返回 undefinedpush 一个元素后 peek 能拿到它。单元素数组[1]建堆、push、pop 都正常。普通数组[3, 1, 4, 1, 5, 9, 2, 6]找前 3 大结果应为 5、6、9顺序可以不同这个过程 30 秒能推完。平时练习可以在浏览器控制台直接跑不需要搭环境。前端人练算法最大的优势就是打开 DevTools 就能验证。6.3 面试中最容易说错的几句话有些说法一出口面试官就知道你是背题还是真懂。我列几个反面例子“堆排序和 sort 差不多”差很多。堆排序不稳定原地空间 O(1)原生 sort 在不同引擎里可能是稳定的归并插入排序。“堆是一棵用链表表示的树”这是最常见的误区。堆的核心是数组连续存储用下标计算父子关系这也是它比普通二叉树更省空间的原因。“堆就是优先队列”严格说优先队列是抽象概念堆是它的常见实现。这样说显得专业得多。6.4 复习节奏建议如果你从零开始准备我建议按下面顺序连续练一周第一天开始每天默写一遍最小堆类目标 5 分钟写完。第二天开始练 TopK 和堆排序。最后练合并 K 个有序链表和数据流中位数因为它们依赖比较器和双堆思维。不要背代码每次写之前先画一遍上浮下沉的路径图。画到第三四天你会发现手写堆从“背诵”变成了“推导”这个过程比结果重要得多。最后分享一个我自己的经验。我第一次手写堆时总想“把这个下沉函数写对再写下一个”结果一步错步步错。后来我改成先画一棵三层小树把插入、删除的路径标出来再对着图写代码正确率提高了很多。另一个习惯是面试开始时先跟面试官确认清楚“数组是静态的还是流式的K 可能等于 n 吗要升序还是降序”这三个问题一确认代码怎么写基本就定了。祝各位前端同学下次手撕堆不是紧张而是兴奋。
