1. 堆不是完整排序
二叉堆是满足堆序的完全二叉树。小顶堆保证父节点不大于孩子,因此根是最小值;它不保证左右兄弟有序,更不保证整个数组升序。优先队列是“按优先级取出”的接口,堆是实现方式之一。
本文统一零基数组:下标 i 的左孩子为 2i + 1,右孩子为 2i + 2,父节点为 Math.floor((i - 1) / 2)。旧文混合一基与零基公式容易出错,不要混用。
2. 最小实现:插入向上,弹出向下
输入值均为有限数值。内部数组只通过类的方法修改;空堆 peek、pop 返回 null。插入后只有新节点到根的路径可能失序;删除根后用末尾元素补根,再沿较小孩子向下调整。
class MinHeap {
constructor() { this.values = []; }
get size() { return this.values.length; }
peek() { return this.size === 0 ? null : this.values[0]; }
push(value) {
const a = this.values;
a.push(value);
let i = a.length - 1;
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (a[parent] <= a[i]) break;
[a[parent], a[i]] = [a[i], a[parent]];
i = parent;
}
}
pop() {
if (this.size === 0) return null;
const a = this.values;
const result = a[0];
const last = a.pop();
if (a.length === 0) return result;
a[0] = last;
let i = 0;
while (i * 2 + 1 < a.length) {
let child = i * 2 + 1;
if (child + 1 < a.length && a[child + 1] < a[child]) child++;
if (a[i] <= a[child]) break;
[a[i], a[child]] = [a[child], a[i]];
i = child;
}
return result;
}
}
function findKthLargest(nums, k) {
if (!Number.isInteger(k) || k < 1 || k > nums.length) {
throw new RangeError('Expected 1 <= k <= input length');
}
const heap = new MinHeap();
for (const value of nums) {
heap.push(value);
if (heap.size > k) heap.pop();
}
return heap.peek();
}查看堆顶为 O(1);插入或弹出的调整路径最长为树高,时间为 O(log n),临时辅助空间为 O(1);堆自身存储为 O(n)。单节点弹出后必须直接返回,不能把刚取出的值又写回空数组。
手推插入 5、2、4、1,每次画父子关系;再连续弹出,得到升序序列。类只保留学习必需的操作,不为对象优先级、取消任务等业务需求增加接口。
3. 为什么第若干大元素使用小顶堆
findKthLargest 的契约是返回第 k 大元素,重复值按出现次数计算,不修改输入。全排序是朴素方法;只保留最大的 k 个值时,不需要排好其余元素。
处理每个元素后,堆中保存已处理前缀里最大的至多 k 个值。多一个就删除最小者,最终堆顶是这些最大值中最小的,也就是第 k 大。不是第 k 个不同值。
上述实现先加入再弹出,堆最多有 k + 1 个元素,时间为 O(n log(k + 1)),空间为 O(k);这样也准确涵盖 k = 1 的线性扫描成本。空输入没有合法的 k,会抛错。
如果只需要一个最大值,直接扫描更简单;只有数据不断到来、或需要保留多个候选时,堆才更有价值。
4. 建堆、堆排序与性能比较
逐个插入建堆最坏为 O(n log n)。自底向上,从最后一个非叶子节点开始向下调整,可做到 O(n):越靠近底层的节点越多,但需要下降的层数越少,不能把每个节点都按根的高度计费。
堆排序使用大顶堆,把最大值换到未排序区间末尾,再缩小堆范围并调整根。已验证实现统一放在排序算法,不在这里维护第二份代码。整体最坏时间为 O(n log n),迭代调整可用常数辅助空间,但交换会破坏相等记录的相对次序,因此不稳定。
快排与堆排序没有对所有数据和环境都成立的速度排名。访问局部性、分区策略、数据分布及常数成本都会影响表现;固定基准快排还可能退化到平方时间。
5. 应用与选学:从堆性质推导方案
| 场景 | 维护内容 | 需要额外考虑的条件 |
|---|---|---|
| 合并多路有序文件 | 每个文件当前最小未输出值 | 输出后只补该文件下一项;总元素数为 N、路数为 k 时约 O(N log(k + 1)) |
| 定时任务 | 按到期时间维护最早任务 | 插入更早任务要调整唤醒;取消与重试需要额外索引或惰性删除 |
| 数据流中位数 | 较小一半的大顶堆、较大一半的小顶堆 | 两堆大小相差至多一,且左堆最大值不大于右堆最小值 |
中位数的插入步骤:先按分界值选择堆,再把过大的堆顶移到另一堆恢复大小平衡。奇数个值取较大堆的根;偶数个值取两根平均,注意数值范围和浮点语义。插入为 O(log n),查询为 O(1),总存储为 O(n)。先手推 5、1、9、2,得到中位数 5、3、5、3.5,再自行实现两个方向的堆。这是完整的选学推导,不是空代码占位。
6. 验证与练习
node --test tests/algorithm-structures-examples.test.mjs每次插入与删除后检查父节点不大于孩子;测试空堆、单值、重复、负数及交错操作。第若干大元素应与排序结果对照,并检查输入不变和非法 k。
闭卷解释:为何弹出时要与两个孩子中较小的交换?为何只比较左孩子会出错?掌握之后再做数据流中位数,避免把堆接口背成一堆方法名。
评论
正在加载评论…