LLY的博客

Appearance

二叉堆算法题分类解析 ​

一、堆的基础概念与识别技巧 ​

堆的特点：

  • 堆是一棵完全二叉树，每个节点的值都不小于（大顶堆）或不大于（小顶堆）其子节点的值
  • 用数组表示时，第 i 个节点的左右孩子下标分别为 i*2+1 和 i*2+2
  • 核心价值：动态维护一组数据的最值，支持 O(log n) 的插入和删除，O(1) 的获取最值

何时使用堆 ：

  1. 需要动态维护最值：数据不断更新，你需要始终能快速拿到当前的最大或最小值
  2. Top K 问题：求前 K 大/小、最频繁的 K 个元素
  3. 需要合并多个有序序列：如合并 K 个有序链表
  4. 需要动态排序：数据流中位数、实时排行榜

二、Top K 问题（最经典） ​

类型特点：求前 K 大通常用小顶堆（堆顶是门槛，只有比门槛大的才进来），求前 K 小通常用大顶堆。维护一个大小为 K 的堆，遍历一次即可 。

难度题目核心思路简介
中等215. 数组中的第K个最大元素维护大小为 K 的最小堆，堆顶即为第 K 大
中等347. 前 K 个高频元素哈希表统计频率 + 最小堆维护 Top K
中等692. 前K个高频单词类似 347，注意排序规则（频率降序，字典序升序）
中等973. 最接近原点的 K 个点计算距离后维护最大堆（或最小堆 + 排序）
中等378. 有序矩阵中第 K 小的元素二分法或最小堆（多路归并思想）
困难719. 找出第 K 小的数对距离二分答案 + 双指针，堆解法也可行

三、数据流与动态中位数 ​

类型特点：数据是动态到达的，需要实时维护当前的中位数或最值。常用技巧是对顶堆：一个大顶堆维护较小的一半，一个小顶堆维护较大的一半 。

难度题目核心思路简介
困难295. 数据流的中位数对顶堆：大顶堆放较小半，小顶堆放较大半，保持平衡
简单703. 数据流中的第 K 大元素维护大小为 K 的最小堆，堆顶即为第 K 大
中等480. 滑动窗口中位数对顶堆 + 延迟删除（较复杂）

四、合并与连接问题 ​

类型特点：多个有序序列合并成一个有序序列，每次取当前最小的元素，适合用最小堆。

难度题目核心思路简介
困难23. 合并K个升序链表将每个链表头节点放入最小堆，依次弹出并加入下一个节点
中等1167. 连接棒材的最低费用（会员）哈夫曼编码思想，每次取最小的两个合并
中等373. 查找和最小的 K 对数字最小堆，每次从堆顶取一对，加入下一对候选
困难632. 最小区间最小堆维护当前每个列表的指针，记录最大最小值

五、任务调度与贪心 ​

类型特点：任务有优先级或冷却时间，需要合理安排顺序。通常用最大堆动态取当前最紧急的任务。

难度题目核心思路简介
中等621. 任务调度器贪心 + 最大堆，每个周期取出 n+1 个不同任务
中等767. 重构字符串最大堆按频率取字符，每次取两个不同的拼接
困难358. K 距离间隔重排字符串（会员）类似 767，但间隔要求更严格
困难502. IPO贪心 + 堆，每次从可达项目中选利润最大的

六、区间与会议安排 ​

类型特点：区间重叠、会议室安排等问题，常用最小堆维护当前正在使用的资源。

难度题目核心思路简介
中等253. 会议室 II（会员）按开始时间排序，最小堆维护结束时间，判断是否需要新会议室
困难218. 天际线问题扫描线 + 最大堆维护当前高度
困难407. 接雨水 IIBFS + 最小堆，从边界向内收缩

七、其他经典堆问题 ​

难度题目核心思路简介
困难239. 滑动窗口最大值虽可用单调队列更优，但堆 + 延迟删除也可解
中等264. 丑数 II最小堆 + 哈希去重，或用三指针 DP
中等313. 超级丑数类似 264，但质数列表是给定的
中等355. 设计推特哈希表 + 优先队列实现推文推送
中等451. 根据字符出现频率排序哈希表统计频率后，可用最大堆排序

堆的解题模板（JavaScript） ​

1. JavaScript 中的堆 ​

JavaScript 没有原生堆，但可以用数组模拟，借助第三方库（如 heap）或手写。在力扣中，通常手写或用数组模拟简单场景。对于复杂场景，建议掌握手写最小堆/最大堆的能力。

2. 最小堆模板（手写） ​

javascript
class MinHeap {
    constructor() {
        this.heap = [];
    }
    
    // 获取父节点下标
    getParentIndex(i) { return Math.floor((i - 1) / 2); }
    getLeftChildIndex(i) { return i * 2 + 1; }
    getRightChildIndex(i) { return i * 2 + 2; }
    
    // 交换
    swap(i, j) {
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
    }
    
    // 上浮
    up(index) {
        if (index === 0) return;
        const parent = this.getParentIndex(index);
        if (this.heap[parent] > this.heap[index]) {
            this.swap(parent, index);
            this.up(parent);
        }
    }
    
    // 下沉
    down(index) {
        const left = this.getLeftChildIndex(index);
        const right = this.getRightChildIndex(index);
        let min = index;
        if (left < this.heap.length && this.heap[left] < this.heap[min]) {
            min = left;
        }
        if (right < this.heap.length && this.heap[right] < this.heap[min]) {
            min = right;
        }
        if (min !== index) {
            this.swap(min, index);
            this.down(min);
        }
    }
    
    // 插入
    push(val) {
        this.heap.push(val);
        this.up(this.heap.length - 1);
    }
    
    // 弹出堆顶
    pop() {
        if (this.heap.length === 0) return null;
        const top = this.heap[0];
        const last = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = last;
            this.down(0);
        }
        return top;
    }
    
    // 查看堆顶
    peek() {
        return this.heap.length > 0 ? this.heap[0] : null;
    }
    
    size() {
        return this.heap.length;
    }
}

3. 最大堆模板（可通过最小堆取负数实现） ​

javascript
// 存数据时存 -val，取出时取 -top

4. Top K 模板（小顶堆） ​

javascript
function findKthLargest(nums, k) {
    const heap = new MinHeap();
    for (const num of nums) {
        heap.push(num);
        if (heap.size() > k) {
            heap.pop();
        }
    }
    return heap.peek();
}

5. 对顶堆模板（数据流中位数） ​

javascript
class MedianFinder {
    constructor() {
        this.maxHeap = new MaxHeap(); // 存较小的一半
        this.minHeap = new MinHeap(); // 存较大的一半
    }
    
    addNum(num) {
        if (this.maxHeap.size() === 0 || num <= this.maxHeap.peek()) {
            this.maxHeap.push(num);
        } else {
            this.minHeap.push(num);
        }
        // 平衡两个堆
        if (this.maxHeap.size() > this.minHeap.size() + 1) {
            this.minHeap.push(this.maxHeap.pop());
        } else if (this.minHeap.size() > this.maxHeap.size()) {
            this.maxHeap.push(this.minHeap.pop());
        }
    }
    
    findMedian() {
        if (this.maxHeap.size() === this.minHeap.size()) {
            return (this.maxHeap.peek() + this.minHeap.peek()) / 2;
        }
        return this.maxHeap.peek();
    }
}

刷题建议 ​

  1. 基础入门：215. 数组中的第K个最大元素 → 703. 数据流中的第 K 大元素
  2. Top K 进阶：347. 前 K 个高频元素 → 692. 前K个高频单词
  3. 合并与连接：23. 合并K个升序链表 → 373. 查找和最小的 K 对数字
  4. 对顶堆应用：295. 数据流的中位数 → 480. 滑动窗口中位数
  5. 贪心与调度：621. 任务调度器 → 767. 重构字符串

Released under the MIT License.

Copyright © 2026