堆和优先队列深入
掌握二叉堆、堆操作、优先队列和堆排序。
你将学到
- 二叉堆性质和数组表示
- 堆操作:插入、提取、堆化
- 优先队列应用
- 堆排序及其 O(n log n) 保证
概念讲解
堆和优先队列深入
堆是完全二叉树,每个父节点 <=(最小堆)或 >=(最大堆)其子节点。堆性质保证最小(或最大)值总在根处,O(1) 可访问。
数组表示
完全二叉树可存储在数组中而无需指针:索引 i 的子节点在 2i+1 和 2i+2,i 的父节点在 (i-1)/2(整除)。这缓存友好且避免指针开销。
核心操作
插入(O(log n)):在末尾添加,然后上浮。提取最小/最大(O(log n)):取根,将最后元素移到根,然后下沉。堆化(O(n)):从中索引到 0 下沉,从无序数组构建堆。
优先队列
优先队列是抽象数据类型,每个元素有优先级;出队返回最高优先级元素。堆是标准实现。应用:Dijkstra 算法、哈夫曼编码、事件驱动仿真、任务调度。
堆排序
堆排序以 O(n) 建堆,然后反复提取最大值到数组末尾。最坏 O(n log n),原地(O(1) 额外空间),但不稳定。它是唯一既最坏 O(n log n) 又原地的常见排序。
示例代码
class PriorityQueue {
constructor(compare = (a, b) => a < b) { this.h = []; this.compare = compare; }
push(x) {
this.h.push(x); let i = this.h.length - 1;
while (i > 0) { const p = (i - 1) >> 1; if (!this.compare(this.h[i], this.h[p])) break; [this.h[i], this.h[p]] = [this.h[p], this.h[i]]; i = p; }
}
pop() {
const top = this.h[0]; const last = this.h.pop();
if (this.h.length > 0) {
this.h[0] = last; let i = 0, n = this.h.length;
while (true) { let s = i, l = 2*i+1, r = 2*i+2; if (l < n && this.compare(this.h[l], this.h[s])) s = l; if (r < n && this.compare(this.h[r], this.h[s])) s = r; if (s === i) break; [this.h[i], this.h[s]] = [this.h[s], this.h[i]]; i = s; }
}
return top;
}
get size() { return this.h.length; }
}
const pq = new PriorityQueue((a, b) => a.priority < b.priority);
pq.push({task: 'render', priority: 1}); pq.push({task: 'fetch', priority: 3}); pq.push({task: 'log', priority: 2});
while (pq.size) console.log(pq.pop().task);
优先队列使用比较函数确定顺序。push 上浮,pop 下沉。任务调度器先处理最高优先级的任务。
动手试一试
- Crontab Generator
调度作业常用优先队列——观察优先级如何影响执行顺序。
常见错误
错误写法
用有序数组代替堆实现优先队列。
正确做法
有序数组插入为 O(n)。堆给出 O(log n) 插入和提取——动态优先队列用它。
错误写法
混淆最小堆和最大堆。
正确做法
最小堆根是最小值;最大堆根是最大值。保持一致——混用产生错误结果。
查阅不认识的术语
新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。
动手做项目
通过引导式项目应用所学,含起始代码与解决方案。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。