二叉堆算法题解题思路与代码分析
一、Top K 问题
核心解题思路：
- 求前 K 大：维护一个大小为 K 的最小堆，堆顶是当前第 K 大的门槛。遍历数组，当堆大小不足 K 时直接入堆；当堆已满且当前元素大于堆顶时，弹出堆顶，将当前元素入堆。最终堆顶即为第 K 大。
- 求前 K 高频：先用哈希表统计频率，再将 [频率, 元素] 放入大小为 K 的最小堆，按频率比较。
经典例题：215. 数组中的第K个最大元素
题目：给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
javascript
/**
* 最小堆实现
*/
class MinHeap {
constructor() {
this.heap = [];
}
push(val) {
this.heap.push(val);
this.bubbleUp(this.heap.length - 1);
}
pop() {
const min = this.heap[0];
const last = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = last;
this.sinkDown(0);
}
return min;
}
size() {
return this.heap.length;
}
peek() {
return this.heap[0];
}
bubbleUp(index) {
while (index > 0) {
const parent = Math.floor((index - 1) / 2);
if (this.heap[parent] > this.heap[index]) {
[this.heap[parent], this.heap[index]] = [this.heap[index], this.heap[parent]];
index = parent;
} else {
break;
}
}
}
sinkDown(index) {
const length = this.heap.length;
while (true) {
let leftChild = 2 * index + 1;
let rightChild = 2 * index + 2;
let swap = null;
if (leftChild < length && this.heap[leftChild] < this.heap[index]) {
swap = leftChild;
}
if (rightChild < length) {
if ((swap === null && this.heap[rightChild] < this.heap[index]) ||
(swap !== null && this.heap[rightChild] < this.heap[leftChild])) {
swap = rightChild;
}
}
if (swap === null) break;
[this.heap[index], this.heap[swap]] = [this.heap[swap], this.heap[index]];
index = swap;
}
}
}
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var findKthLargest = function(nums, k) {
const minHeap = new MinHeap();
for (const num of nums) {
minHeap.push(num);
if (minHeap.size() > k) {
minHeap.pop(); // 保持堆大小为 k
}
}
return minHeap.peek(); // 堆顶即第 k 大
};关键点：
- 最小堆中始终保留当前遍历过的元素中最大的 k 个，堆顶是这 k 个中最小的，也就是整个数组中第 k 大的。
- 时间复杂度 O(n log k)，空间复杂度 O(k)。
经典例题：347. 前 K 个高频元素
题目：给你一个整数数组 nums 和一个整数 k，请你返回其中出现频率前 k 高的元素。
javascript
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var topKFrequent = function(nums, k) {
// 1. 统计频率
const freqMap = new Map();
for (const num of nums) {
freqMap.set(num, (freqMap.get(num) || 0) + 1);
}
// 2. 最小堆，存储 [频率, 元素]
const minHeap = new MinHeap(); // 需改造：比较频率
// 为了直接使用上面的 MinHeap，可以存储 [freq, num]，并修改比较逻辑
// 这里为了简洁，改用数组手动维护堆（或使用优先队列库，但手写同理）
const heap = [];
const compare = (a, b) => a[0] - b[0]; // 按频率升序
for (const [num, freq] of freqMap) {
heap.push([freq, num]);
// 上浮
let idx = heap.length - 1;
while (idx > 0) {
const parent = Math.floor((idx - 1) / 2);
if (compare(heap[parent], heap[idx]) > 0) {
[heap[parent], heap[idx]] = [heap[idx], heap[parent]];
idx = parent;
} else break;
}
if (heap.length > k) {
// 弹出堆顶（最小频率）
heap[0] = heap.pop();
// 下沉
let i = 0;
while (true) {
let left = i * 2 + 1;
let right = i * 2 + 2;
let smallest = i;
if (left < heap.length && compare(heap[left], heap[smallest]) < 0) smallest = left;
if (right < heap.length && compare(heap[right], heap[smallest]) < 0) smallest = right;
if (smallest !== i) {
[heap[i], heap[smallest]] = [heap[smallest], heap[i]];
i = smallest;
} else break;
}
}
}
return heap.map(item => item[1]); // 返回元素
};关键点：
- 核心思想：维护大小为 k 的最小堆，堆顶是当前第 k 高的频率。
- 需注意堆中元素是 [频率, 元素] 对，比较时按频率。
- 最终堆中留下的就是频率最高的 k 个元素。
二、数据流与动态中位数
核心解题思路：
- 对顶堆：一个大顶堆维护较小的一半，一个小顶堆维护较大的一半，并保持两个堆大小平衡（或大顶堆多一个元素）。
- 插入元素时先决定插入哪个堆，然后调整平衡。
- 中位数 = 若两堆大小相等，则为两堆顶的平均值；否则为大顶堆堆顶。
经典例题：295. 数据流的中位数
题目：设计一个支持以下两种操作的数据结构：addNum 添加整数，findMedian 返回当前所有元素的中位数。
javascript
class MedianFinder {
constructor() {
this.maxHeap = []; // 大顶堆，存放较小的一半（用负数模拟）
this.minHeap = []; // 小顶堆，存放较大的一半
}
// 大顶堆比较：b - a（因为存负数，实际比较的是原值的相反数）
// 小顶堆比较：a - b
// 为简化，直接用 push 后调用自定义的堆调整，或使用第三方库。这里用数组模拟并手动调整。
// 为节省篇幅，这里展示使用两个数组并手动维护堆的调整逻辑，但实际可封装成类。
// 为清晰，使用两个数组并每次插入后排序的方法（效率低，仅示意）。实际生产应使用堆。
// 但力扣上可以用数组配合 sort，但效率低，建议手写堆。
// 此处演示一种简单写法：使用两个堆，用 push 和 pop 时手动调整。
// 为简化，我们使用一个技巧：大顶堆存负数，这样就可以共用小顶堆逻辑。
// 实际实现时，建议封装两个堆类。这里为了篇幅，使用数组模拟并调用 adjust。
// 我们给出核心逻辑：
addNum(num) {
// 先插入大顶堆（较小的一半）
if (this.maxHeap.length === 0 || num <= -this.maxHeap[0]) {
this.maxHeap.push(-num); // 存负数
this.up(this.maxHeap, this.maxHeap.length - 1, (a, b) => a > b); // 大顶堆：父节点 > 子节点
} else {
this.minHeap.push(num);
this.up(this.minHeap, this.minHeap.length - 1, (a, b) => a < b); // 小顶堆：父节点 < 子节点
}
// 平衡两个堆的大小
if (this.maxHeap.length > this.minHeap.length + 1) {
// 将大顶堆堆顶移到小顶堆
const val = -this.maxHeap[0];
this.maxHeap[0] = this.maxHeap[this.maxHeap.length - 1];
this.maxHeap.pop();
this.down(this.maxHeap, 0, (a, b) => a > b);
this.minHeap.push(val);
this.up(this.minHeap, this.minHeap.length - 1, (a, b) => a < b);
} else if (this.minHeap.length > this.maxHeap.length) {
const val = this.minHeap[0];
this.minHeap[0] = this.minHeap[this.minHeap.length - 1];
this.minHeap.pop();
this.down(this.minHeap, 0, (a, b) => a < b);
this.maxHeap.push(-val);
this.up(this.maxHeap, this.maxHeap.length - 1, (a, b) => a > b);
}
}
findMedian() {
if (this.maxHeap.length > this.minHeap.length) {
return -this.maxHeap[0];
} else {
return (-this.maxHeap[0] + this.minHeap[0]) / 2;
}
}
// 上浮，compare 为比较函数：a 父节点，b 子节点，应返回 true 表示需要交换
up(heap, i, compare) {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (compare(heap[parent], heap[i])) {
[heap[parent], heap[i]] = [heap[i], heap[parent]];
i = parent;
} else break;
}
}
down(heap, i, compare) {
const n = heap.length;
while (true) {
let left = i * 2 + 1;
let right = i * 2 + 2;
let target = i;
if (left < n && compare(heap[target], heap[left])) target = left;
if (right < n && compare(heap[target], heap[right])) target = right;
if (target !== i) {
[heap[i], heap[target]] = [heap[target], heap[i]];
i = target;
} else break;
}
}
}关键点：
- 使用两个堆，大顶堆放较小的一半（实际存负数以复用上浮/下沉逻辑），小顶堆放较大的一半。
- 每次插入后调整两堆大小，保证大顶堆大小 ≥ 小顶堆，且差值不超过 1。
- 获取中位数时根据两堆大小计算。
三、合并与连接问题
核心解题思路：
- 合并 K 个有序序列：将每个序列的当前最小元素（如链表头节点）放入最小堆，每次弹出堆顶，然后将该序列的下一个元素加入堆。
- 哈夫曼编码类型：每次取最小的两个元素合并，重新放入堆，直到只剩一个。
经典例题：23. 合并K个升序链表
题目：给你一个链表数组，每个链表都已经按升序排列，请你将所有链表合并到一个升序链表中。
javascript
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
// 最小堆，基于链表节点值
class MinHeap {
constructor() {
this.heap = [];
}
push(node) {
this.heap.push(node);
this.up(this.heap.length - 1);
}
pop() {
const top = this.heap[0];
const last = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = last;
this.down(0);
}
return top;
}
up(i) {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (this.heap[parent].val > this.heap[i].val) {
[this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
i = parent;
} else break;
}
}
down(i) {
const n = this.heap.length;
while (true) {
let left = i * 2 + 1;
let right = i * 2 + 2;
let min = i;
if (left < n && this.heap[left].val < this.heap[min].val) min = left;
if (right < n && this.heap[right].val < this.heap[min].val) min = right;
if (min !== i) {
[this.heap[i], this.heap[min]] = [this.heap[min], this.heap[i]];
i = min;
} else break;
}
}
size() {
return this.heap.length;
}
}
const dummy = new ListNode(0);
let cur = dummy;
const heap = new MinHeap();
// 将所有链表头节点加入堆
for (const list of lists) {
if (list) heap.push(list);
}
while (heap.size() > 0) {
const node = heap.pop();
cur.next = node;
cur = cur.next;
if (node.next) heap.push(node.next);
}
return dummy.next;
};关键点：
- 堆中元素是链表节点，按节点值排序。
- 每次弹出最小值节点，将其 next 节点入堆，直至堆空。
- 时间复杂度 O(n log k)，n 为总节点数，k 为链表数。
四、任务调度与贪心
核心解题思路：
- 通常需要用最大堆动态获取当前最紧急（出现次数最多）的任务。
- 对于有冷却时间的问题，模拟时间线，每个周期从堆中取出任务执行，若任务剩余次数不为零则等待冷却后重新入堆。
经典例题：621. 任务调度器
题目：给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表，以及一个冷却时间 n。在任意两个相同种类的任务之间必须至少有长度为 n 的冷却时间。计算完成任务所需的最短时间。
javascript
/**
* @param {character[]} tasks
* @param {number} n
* @return {number}
*/
var leastInterval = function(tasks, n) {
// 1. 统计频率
const freq = new Array(26).fill(0);
for (const c of tasks) {
freq[c.charCodeAt(0) - 'A'.charCodeAt(0)]++;
}
// 2. 最大堆（用数组模拟，每次取最大值，可排序后取最大，但效率低）
// 这里用最大堆，但为了简单，用数组并每次排序（时间复杂度高，但直观）
const maxHeap = [];
for (const count of freq) {
if (count > 0) maxHeap.push(count);
}
maxHeap.sort((a, b) => b - a); // 降序
let time = 0;
while (maxHeap.length > 0) {
// 每一轮取出 n+1 个任务（如果有）
const temp = [];
for (let i = 0; i <= n; i++) {
if (maxHeap.length > 0) {
const count = maxHeap.shift(); // 取最大（已排序，第一个最大）
if (count - 1 > 0) temp.push(count - 1);
}
time++;
if (maxHeap.length === 0 && temp.length === 0) break;
}
// 将剩余次数放回堆并重新排序
for (const count of temp) {
maxHeap.push(count);
}
maxHeap.sort((a, b) => b - a); // 重新降序
}
return time;
};关键点：
- 核心思想：每轮（冷却时间内）尽量安排不同的任务，若不够则闲置。
- 使用最大堆保证每次优先安排剩余次数最多的任务。
- 时间复杂度 O(时间 * n)，若任务种类少则可行，更优解法是贪心公式。
五、区间与会议安排
核心解题思路：
- 区间重叠问题常需按开始时间排序，然后用最小堆维护当前会议的结束时间。
- 新会议开始时，若堆顶的结束时间 ≤ 当前开始时间，则弹出堆顶（会议室释放），否则需要新会议室。
经典例题：253. 会议室 II（会员题，但思路重要）
题目：给定一个会议时间安排的数组 intervals，每个会议时间包含开始和结束时间，你需要计算至少需要多少间会议室才能满足所有会议的安排。
javascript
/**
* @param {number[][]} intervals
* @return {number}
*/
var minMeetingRooms = function(intervals) {
if (!intervals.length) return 0;
// 按开始时间排序
intervals.sort((a, b) => a[0] - b[0]);
// 最小堆，存储结束时间
const minHeap = [intervals[0][1]];
// 手动维护最小堆（简化：使用数组 push 并排序，但效率低）
// 这里用堆的 push 和 pop 逻辑
function push(val) {
minHeap.push(val);
let i = minHeap.length - 1;
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (minHeap[parent] > minHeap[i]) {
[minHeap[parent], minHeap[i]] = [minHeap[i], minHeap[parent]];
i = parent;
} else break;
}
}
function pop() {
const top = minHeap[0];
const last = minHeap.pop();
if (minHeap.length > 0) {
minHeap[0] = last;
let i = 0;
while (true) {
let left = i * 2 + 1;
let right = i * 2 + 2;
let min = i;
if (left < minHeap.length && minHeap[left] < minHeap[min]) min = left;
if (right < minHeap.length && minHeap[right] < minHeap[min]) min = right;
if (min !== i) {
[minHeap[i], minHeap[min]] = [minHeap[min], minHeap[i]];
i = min;
} else break;
}
}
return top;
}
function peek() { return minHeap[0]; }
for (let i = 1; i < intervals.length; i++) {
// 如果当前会议开始时间 >= 最早结束的会议，则复用会议室
if (intervals[i][0] >= peek()) {
pop(); // 移除旧的结束时间
}
push(intervals[i][1]); // 加入当前会议的结束时间
}
return minHeap.length;
};关键点：
- 最小堆始终维护当前正在使用的会议室的结束时间。
- 新会议开始时，若堆顶（最早结束时间）≤ 当前开始时间，则说明有会议室已空，可复用；否则需要新会议室。
- 最后堆的大小即为所需会议室数量。
六、其他经典堆问题
经典例题：239. 滑动窗口最大值（堆 + 延迟删除）
题目：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧。你只可以看到在滑动窗口内的 k 个数字。返回滑动窗口中的最大值。
javascript
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
// 最大堆，存储 [值, 下标]
const maxHeap = [];
const result = [];
function push(val, index) {
maxHeap.push([val, index]);
let i = maxHeap.length - 1;
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (maxHeap[parent][0] < maxHeap[i][0]) { // 最大堆
[maxHeap[parent], maxHeap[i]] = [maxHeap[i], maxHeap[parent]];
i = parent;
} else break;
}
}
function pop() {
const top = maxHeap[0];
const last = maxHeap.pop();
if (maxHeap.length > 0) {
maxHeap[0] = last;
let i = 0;
while (true) {
let left = i * 2 + 1;
let right = i * 2 + 2;
let max = i;
if (left < maxHeap.length && maxHeap[left][0] > maxHeap[max][0]) max = left;
if (right < maxHeap.length && maxHeap[right][0] > maxHeap[max][0]) max = right;
if (max !== i) {
[maxHeap[i], maxHeap[max]] = [maxHeap[max], maxHeap[i]];
i = max;
} else break;
}
}
return top;
}
function peek() {
return maxHeap[0];
}
for (let i = 0; i < nums.length; i++) {
push(nums[i], i);
// 当窗口形成后 (i >= k-1)
if (i >= k - 1) {
// 移除不在窗口内的堆顶
while (peek()[1] <= i - k) {
pop();
}
result.push(peek()[0]);
}
}
return result;
};关键点：
- 堆中存储 [值, 下标]，每次取堆顶时检查下标是否还在窗口内，若不在则弹出（延迟删除）。
- 由于每个元素至多入堆出堆一次，时间复杂度 O(n log n)。
总结
以上六个分类基本覆盖了二叉堆的主要应用场景。建议先熟练掌握 Top K 和 合并有序序列 的基本模板，再挑战 对顶堆、任务调度 等进阶题型。如果遇到困难，可以结合手写堆的练习加深理解。