跳到主要内容

堆与优先级队列 (Heaps & Priority Queues)

为什么堆很重要​

堆提供了对最小或最大元素的高效访问——这对于基于优先级的处理至关重要：

  • 任务调度：操作系统进程调度、异步作业队列。
  • 图算法：Dijkstra 最短路径、Prim 最小生成树。
  • 流处理：在持续的数据流中寻找前 K 个最大/最小元素。
  • 事件模拟：按时间顺序精准处理离散事件。

实际影响：Java 的 PriorityQueue 利用二叉堆实现了 O(log⁡n)O(\log n) 的插入和 O(1)O(1) 的最值访问。从 100 万个元素中找出前 10 名，使用堆仅需约 20 次操作，而全量排序则需 1000 万次比较。

核心概念​

二叉堆结构​

堆是一棵完全二叉树，且满足堆属性：

  • 最大堆 (Max-Heap)：父节点的值 ≥\ge 子节点。
  • 最小堆 (Min-Heap)：父节点的值 ≤\le 子节点。

数组实现原理​

二叉堆通常用数组存储，逻辑结构与物理索引的映射公式如下： 对于索引为 i 的节点：

  • 父节点：(i - 1) / 2
  • 左子节点：2i + 1
  • 右子节点：2i + 2

深入理解​

1. 堆化操作 (Heapify)​

  • 上浮 (Bubble Up)：插入新元素到末尾后，不断与父节点比较并交换，直到满足堆属性。
  • 下沉 (Bubble Down)：删除堆顶后，将末尾元素移至顶部，不断与较大的子节点交换，直到“沉”到正确位置。

2. O(n) 建堆法​

原理：从最后一个非叶子节点开始，由下至上依次执行下沉操作。

  • 数学证明：虽然单次下沉最坏是 O(log⁡n)O(\log n)，但由于大部分节点分布在底层（高度小），总复杂度收敛于 O(n)O(n)。

常见陷阱与规避​

  1. 在循环中使用 heap.size()：若循环体内有 poll() 操作，size 会动态变化导致遍历不全。
    • 对策：使用 while (!heap.isEmpty())。
  2. Comparable 缺失：自定义对象若未实现 Comparable 接口或提供 Comparator，PriorityQueue 会在运行时抛出 ClassCastException。
  3. 内存溢出：在处理无限流时，若不限制堆的大小（如 Top K 场景），会导致 OOM。

实战应用​

合并 K 个有序链表​

思路：将 K 个链表的头节点放入最小堆。每次弹出堆顶元素，并将其下一个节点补入堆中。复杂度 O(Nlog⁡K)O(N \log K)。

数据流的中位数​

思路：使用两个堆。一个最大堆存储较小的一半，一个最小堆存储较大的一半。保持两个堆的大小差不超过 1，中位数即为堆顶。

面试高频题​

Q1: 数组中的第 K 个最大元素 (中等)​

思路：维护一个大小为 kk 的最小堆。遍历结束后，堆顶即为目标值。时间复杂度 O(nlog⁡k)O(n \log k)。

Q2: 前 K 个高频元素 (中等)​

思路：HashMap 统计频率 + 最小堆。

Q3: 任务调度器 (中等)​

思路：最大堆存储剩余任务数，配合冷冻队列（Queue）管理冷却时间。

延伸阅读​

  • Dijkstra 算法：了解堆如何将路径搜索优化到极致。
  • 堆排序：掌握 O(1)O(1) 额外空间、稳定的 O(nlog⁡n)O(n \log n) 排序。
  • 斐波那契堆：探索理论上更优但实现更复杂的堆结构。
  • LeetCode：堆标签题目 stone