Skip to content

堆和优先队列深入

掌握二叉堆、堆操作、优先队列和堆排序。

你将学到

  • 二叉堆性质和数组表示
  • 堆操作:插入、提取、堆化
  • 优先队列应用
  • 堆排序及其 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 等等。

查看术语表

动手做项目

通过引导式项目应用所学,含起始代码与解决方案。

查看项目

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误