illegalCreed

中文

English

中文

English

Appearance

堆的工程应用：优先队列与 Top-K ​

基于通用算法套路 · 核于 2026-07

速查 ​

  • 优先队列（Priority Queue）：抽象数据类型——元素带「优先级」，出队永远取优先级最高（最大或最小）的那个，而非按入队顺序。堆是它的标准实现：入队 = push（O(log n)），出队 = pop 堆顶（O(log n)），查看队首 = peek（O(1)）。
  • 优先队列 vs 普通队列：普通队列 FIFO（先进先出）；优先队列按优先级出队——堆让「取最高优先级」O(1)、维护 O(log n)。
  • Top-K 问题：从 n 个元素中找最大（或最小）的 K 个。最优解用堆：求前 K 大用大小为 K 的小根堆（新元素比堆顶大就替换堆顶）；求前 K 小用大小为 K 的大根堆。
  • Top-K 复杂度：堆方法 O(n log K) 时间、O(K) 空间——当 K ≪ n 时远优于排序的 O(n log n)；尤其适合数据流（无法全部排序的场景）。
  • 为什么求前 K 大用小根堆：小根堆堆顶是当前 K 个里的最小值（门槛），新元素只有比这个门槛大才有资格进堆；最终堆里留下来的就是全局前 K 大。
  • 合并 K 个有序链表：K 个链表各取首元素入小根堆，每次弹出最小接到结果尾，再从该链表补一个入堆——O(N log K)，N 是总节点数。
  • Dijkstra 堆优化：最短路算法中用小根堆维护「当前最短的未确定节点」，把「找最小」从 O(V) 降到 O(log V)，总复杂度 O((V+E) log V)。
  • Prim 最小生成树：同理用小根堆维护「横切边」的最小权重边，每次取最小——细节在图算法叶。
  • 定时器 / 任务调度：定时任务按到期时间入小根堆，最早到期的在堆顶；线程池任务按优先级入堆。
  • 各语言堆：Java PriorityQueue、C++ priority_queue/make_heap、Python heapq、Go container/heap、JS 无原生堆需手写。
  • 进阶顺序：优先队列 → Top-K → 图算法堆优化（Dijkstra/Prim 细节在图算法叶）。

一、优先队列：堆的标准应用 ​

优先队列（Priority Queue, PQ） 是一个抽象数据类型：每个元素带一个优先级（priority），出队操作永远返回当前队列里优先级最高的元素（约定最大或最小），而不是按入队的先后顺序。

操作普通队列（FIFO）优先队列
入队push 尾部 O(1)push 入堆 O(log n)
出队pop 头部 O(1)pop 堆顶（最高优先级）O(log n)
查看队首最早入队的 O(1)最高优先级的 O(1)
顺序先进先出按优先级

堆天然契合优先队列：堆顶就是最高优先级，入队即插入（sift up），出队即删堆顶（sift down）。所以「优先队列」与「堆」在日常语境里几乎等价——语言库里的优先队列类底层都是堆。

js
// 用前面堆的核心操作封装一个优先队列（小根堆，数字小的优先级高）
class PriorityQueue {
  constructor(compare = (a, b) => a - b) { this.heap = []; this.compare = compare; }
  push(x) { /* 追加 + sift up，按 compare 决定大小关系 */ }
  pop()   { /* 删堆顶 + sift down */ }
  peek()  { return this.heap[0]; } // O(1) 看最高优先级
  size()  { return this.heap.length; }
}

典型场景：操作系统的进程调度（按优先级选进程）、医院分诊（按病情轻重）、任务队列（高优先级任务先执行）、定时器（按到期时间排序）。核心都是「动态维护一个集合，反复取最值」。

二、Top-K 问题：堆的高频应用 ​

Top-K 问题：从 n 个元素中找出最大（或最小）的 K 个。这是堆最高频的应用场景，也是面试必考。

为什么求前 K 大用「小根堆」 ​

反直觉但关键：求前 K 大，维护一个大小为 K 的小根堆。原理：

  • 小根堆的堆顶是当前堆里（K 个元素中）的最小值，相当于一个门槛。
  • 遍历剩余元素，只有比这个门槛大的才有资格进堆（淘汰掉当前的堆顶最小值）。
  • 遍历结束后，堆里剩下的 K 个就是全局前 K 大。
js
// 求数组前 K 大的元素（小根堆法）
function topK(arr, k) {
  const heap = []; // 小根堆，大小最多 k
  for (const x of arr) {
    heap.push(x); siftUp(heap, heap.length - 1); // 入堆
    if (heap.length > k) pop(heap);              // 超过 k 就弹出最小的（堆顶）
  }
  return heap; // 堆里就是前 K 大
}
  • 复杂度：每个元素入堆 O(log K)、超容弹出 O(log K)，共 O(n log K) 时间、O(K) 空间。
  • 为什么不用排序：排序 O(n log n)，当 K ≪ n 时 Top-K 的 O(n log K) 更快；且排序需要全部数据就绪，Top-K 能处理数据流（边来边维护，内存只存 K 个）。

三种解法对比 ​

方法时间空间适用
全排序取前 KO(n log n)O(n)数据小、K 接近 n
快速选择（partition）O(n) 平均O(1)一次性查询、不需有序
堆（小根堆求前 K 大）O(n log K)O(K)数据流、K 小、动态

堆方法的优势：内存只用 O(K)，适合 K 很小但 n 很大（如百万级数据找前 10），或数据流式到来（无法一次全装入内存）。

三、合并 K 个有序链表 ​

经典应用：K 个已排序的链表，合并成一个有序链表。用小根堆每次取全局最小：

js
// 合并 K 个有序链表（值小的在前）
function mergeKLists(lists) {
  const heap = new PriorityQueue((a, b) => a.val - b.val); // 按 val 小根堆
  for (const head of lists) if (head) heap.push(head);     // 各链表头入堆
  const dummy = { next: null }; let tail = dummy;
  while (heap.size() > 0) {
    const node = heap.pop();          // 弹出当前最小的节点
    tail.next = node; tail = node;    // 接到结果尾
    if (node.next) heap.push(node.next); // 该链表补一个入堆
  }
  return dummy.next;
}
  • 复杂度：N 个总节点，每个入堆出堆各 O(log K)，共 O(N log K)，优于两两合并的 O(NK)。
  • 堆的大小始终 ≤ K（每个链表最多一个代表在堆里），空间 O(K)。

四、Dijkstra 与 Prim 的堆优化（引入） ​

图算法中「反复取当前最短 / 最小」的需求，正是堆的主场。这里只引入思想，细节在图算法叶。

  • Dijkstra 单源最短路：维护「源点到各点的当前最短距离」，每轮取距离最小的未确定节点松弛邻居。朴素法每轮 O(V) 找最小，总 O(V²)；用小根堆优化「找最小」到 O(log V)，总 O((V+E) log V)——稀疏图上大幅提速。
  • Prim 最小生成树：维护「横切边」集合，每轮取权重最小的横切边加入 MST。同样用小根堆优化「取最小边」。

共同点：图算法中所有「动态取最值」的步骤，都把堆作为加速器——把朴素的 O(V) 扫描降到 O(log V)。

五、定时器与任务调度 ​

工程里堆的隐形应用：

  • 定时器（timer wheel / 最小堆定时器）：大量定时任务按到期时间入小根堆（到期时间小的在堆顶），事件循环每轮检查堆顶是否到期、到期就弹出执行。Node.js / Go 的定时器底层都用了类似的最小堆结构。
  • 线程池 / 任务调度：高优先级任务先执行，用优先队列（堆）按优先级取任务。
  • LFU 缓存：按访问频率淘汰，频率最低的在堆顶（也可用双链表+哈希）。

核心模式都是「动态维护一个集合，反复取出当前最值」——这正是堆的设计目标。

六、各语言堆实现速览 ​

语言类型 / 模块默认序变另一种序
JavaPriorityQueue<T>小根堆传 Comparator.reverseOrder()
C++std::priority_queue<T>大根堆配 std::greater<T> 变小根堆
C++std::make_heap / push_heap / pop_heap大根堆配 greater 变小根堆（操作原数组）
Pythonheapq（操作 list）小根堆大根堆用「取负」技巧
Gocontainer/heap自定义（实现接口）接口里反转比较
JavaScript无原生—手写或用 heap-js 等库

JS 无原生堆 是高频考点和工程痛点——面试常要求手写，工程里要么自己实现（见参考的代码模板），要么引入第三方库。这也解释了为什么本叶要详细讲 sift up/down 的实现。

交互演示 ​

下一步 ​

掌握堆的应用后，可深入参考查 sift up/down 代码模板、各语言堆对照与易错点；堆作为排序算法（堆排序）的完整流程在独立叶「堆排序」讲。