当前位置：首页 > news >正文

避坑指南：用 JS 手写 MinHeap 解决 LeetCode “数据流中第 K 大元素” 的三大隐藏陷阱

news 2026/6/17 2:45:43

前言

在刷 LeetCode 703. 数据流中的第 K 大元素（Kth Largest Element in a Stream）时，很多同学为了追求底层的极致理解，都会选择不使用第三方库，纯手写一个小顶堆（MinHeap）。

手写堆的思路非常清晰：保持小顶堆的容量为KKK，每次进来的元素如果比堆顶大，就踢掉堆顶，让其自动堆化。这样堆顶永远是第KKK大的元素。

道理大家都懂，但在用 JavaScript 落地实现的时候，稍不留神就会掉进几个隐蔽的“天坑”里。今天我们就通过代码重构，来聊聊这些让你卡在部分测试用例上的“罪魁祸首”。

极其生动的一个堆比喻

在开始写代码前，我们要搞清楚堆的运作本质。用一个很江湖的视角来看：

堆就像社会阶层。新加入的元素老老实实呆在最底层（数组末尾），然后根据自己的本事和规则往上杀（bubbleUp）。
当最顶层的统治者出堆（pop）时，为了稳住大局，会随手从堆底抓一个最底层的元素上调到堆顶当炮灰。接着，这个炮灰因为实力不足，再一层层地被“降维打击”滤下去（bubbleDown），直到回到属于他的位置。

踩坑分析与重构

我们先来看一段逻辑基本成型，但隐藏了致命 Bug 的bubbleDown调整逻辑：

// ❌ 潜藏危机的实现片段if(leftIndex<length&&this.heap[leftIndex]){if(this.heap[smallest]>this.heap[leftIndex]){smallest=leftIndex;}}

这里面藏了哪些坑？

坑 1：致命的 JavaScript “真假值（Falsy）” 陷阱

在写边界条件时，我们习惯性地写出if (this.heap[leftIndex])来确保节点存在。
但是，如果这个节点的值恰好是0呢？
在 JS 中，0会被判定为false！当测试用例包含0或者负数时，这个分支直接被跳过，导致你的小顶堆在遇到0时直接“罢工”，堆结构瞬间瓦别。

修复方案：必须严谨地判断节点是否为undefined，即this.heap[leftIndex] !== undefined。

坑 2：元素交换时的“原地踏步”

在交换两个数组元素时，我们常用解构赋值。但如果一时手软写成了这样：

// ❌ 相当于把值赋给了自己，根本没有交换[this.heap[index],this.heap[smallest]]=[this.heap[index],this.heap[smallest]];

修复方案：严格对调两边的变量：[this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];

坑 3：`bubbleUp`时的无限循环

在往上“杀”的时候，如果只做了元素交换，忘记更新当前指针的指针（index = parentIndex），那么while (index > 0)就会抱着同一个索引原地死循环，直至调用栈爆炸。

终极完美代码实现

避开所有的坑后，以下是完美通过 LeetCode 全量测试用例的 JS 完整实现：

/** * 精准、稳健的自定义小顶堆 */classMyMinHeap{constructor(){this.heap=[];}// 查看社会最顶层（最小值）peak(){returnthis.heap[0];}// 踢掉最顶层，扶持底层炮灰上台，再将其打压下去pop(){if(this.heap.length===0)returnnull;if(this.heap.length===1)returnthis.heap.pop();constmin=this.heap[0];this.heap[0]=this.heap.pop();// 拿堆底元素顶替this.bubbleDown(0);// 炮灰下沉returnmin;}size(){returnthis.heap.length;}// 新人入堆，从最底层开始凭本事往上杀push(val){this.heap.push(val);this.bubbleUp(this.heap.length-1);}// 向上调整bubbleUp(index){while(index>0){letparentIndex=Math.floor((index-1)/2);// 如果已经比父亲大，说明符合小顶堆规则，停止向上if(this.heap[index]>=this.heap[parentIndex]){break;}// 否则，交换位置[this.heap[index],this.heap[parentIndex]]=[this.heap[parentIndex],this.heap[index]];index=parentIndex;// 🌟 记得更新索引继续往上爬}}// 向下调整bubbleDown(index){letlength=this.heap.length;while(true){letleftIndex=2*index+1;letrightIndex=2*index+2;letsmallest=index;// 🌟 核心防坑：必须使用 !== undefined 兼容数值 0if(leftIndex<length&&this.heap[leftIndex]!==undefined){if(this.heap[smallest]>this.heap[leftIndex]){smallest=leftIndex;}}if(rightIndex<length&&this.heap[rightIndex]!==undefined){if(this.heap[smallest]>this.heap[rightIndex]){smallest=rightIndex;}}// 如果不需要交换，说明已经各就各位，结束堆化if(smallest===index){break;}// 🌟 核心防坑：真正的两数互换[this.heap[index],this.heap[smallest]]=[this.heap[smallest],this.heap[index]];index=smallest;}}}/** * @param {number} k * @param {number[]} nums */varKthLargest=function(k,nums){this.minHeap=newMyMinHeap();this.k=k;for(letnumofnums){this.add(num);}};/** * @param {number} val * @return {number} */KthLargest.prototype.add=function(val){this.minHeap.push(val);// 维持小顶堆的社会规模只有 K 个人// 超过 K 个人时，把最底层的“统治者”（实际上是剩下所有人里最小的那个）赶走if(this.minHeap.size()>this.k){this.minHeap.pop();}// 剩下的里面最小的，就是全局第 K 大的元素returnthis.minHeap.peak();};