Skip to content

1. 堆不是完整排序 ​

二叉堆是满足堆序的完全二叉树。小顶堆保证父节点不大于孩子,因此根是最小值;它不保证左右兄弟有序,更不保证整个数组升序。优先队列是“按优先级取出”的接口,堆是实现方式之一。

本文统一零基数组:下标 i 的左孩子为 2i + 1,右孩子为 2i + 2,父节点为 Math.floor((i - 1) / 2)。旧文混合一基与零基公式容易出错,不要混用。

2. 最小实现:插入向上,弹出向下 ​

输入值均为有限数值。内部数组只通过类的方法修改;空堆 peek、pop 返回 null。插入后只有新节点到根的路径可能失序;删除根后用末尾元素补根,再沿较小孩子向下调整。

js
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. 验证与练习 ​

sh
node --test tests/algorithm-structures-examples.test.mjs

每次插入与删除后检查父节点不大于孩子;测试空堆、单值、重复、负数及交错操作。第若干大元素应与排序结果对照,并检查输入不变和非法 k。

闭卷解释:为何弹出时要与两个孩子中较小的交换?为何只比较左孩子会出错?掌握之后再做数据流中位数,避免把堆接口背成一堆方法名。

评论

正在加载评论…