PriorityQueue（优先队列）详解

一、是什么？

PriorityQueue 是 Java 集合框架中的一个类，位于 java.util 包中。它是一种基于优先级堆的无界队列，元素按照自然顺序或自定义比较器（Comparator）排序。默认实现是小顶堆（最小元素在队首），但可通过比较器改为大顶堆。

---

二、解决什么问题

1. 高效获取最值元素
   普通队列（如LinkedList）按插入顺序访问，而 PriorityQueue 能快速访问/删除当前最小（或最大）元素。
2. 动态排序需求
   当需要持续维护一个有序集合（如新增元素后自动重排序），使用排序算法（如 Collections.sort()）会带来 O(n log n) 开销，PriorityQueue 的堆结构只需 O(log n)。
3. 节省内存
   相比 TreeMap/TreeSet 存储全量排序数据，PriorityQueue 仅需维护堆结构，内存占用更低。

---

三、核心方法

方法	功能	时间复杂度
add(E e) / offer(E e)	插入元素	O(log n)
remove() / poll()	移除并返回队首元素	O(log n)
element() / peek()	查看队首元素（不移除）	O(1)
size()	返回元素数量	O(1)
isEmpty()	判断队列是否为空	O(1)
clear()	清空队列	O(n)

---

四、应用场景（代码题高频考点）

1. Top K 问题
   👉 场景：从海量数据中找出最大/最小的 K 个元素
   ✅ 解法：

   • 最小 K 值 → 大顶堆（队首是当前最大元素）
   • 最大 K 值 → 小顶堆（队首是当前最小元素）

2. 流式数据的中位数
   👉 场景：持续输入数字，动态计算中位数
   ✅ 解法：用两个堆维护数据流

   • 大顶堆存较小一半数字
   • 小顶堆存较大一半数字
   • 保持两堆大小平衡

3. 合并 K 个有序序列
   👉 场景：合并 K 个升序链表/数组
   ✅ 解法：

   • 用小顶堆存储每个序列的当前头节点
   • 每次取堆顶（最小节点）加入结果

4. Dijkstra 最短路径算法
   👉 场景：图论中高效获取未处理的最小距离节点
   ✅ 解法：用小顶堆优化节点选择过程

---

五、Java 示例

1. 基础使用（默认小顶堆）

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);

System.out.println(minHeap.poll()); // 输出 1（最小元素）
System.out.println(minHeap.poll()); // 输出 3

2. 大顶堆实现（解决 Top K 问题）

// 使用比较器反转顺序
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);

// JDK 8+ 简洁写法
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

3. 合并 K 个有序链表（LeetCode 23）

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode node : lists) {
        if (node != null) heap.offer(node);
    }
    
    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;
    while (!heap.isEmpty()) {
        ListNode min = heap.poll();
        cur.next = min;
        cur = cur.next;
        if (min.next != null) heap.offer(min.next);
    }
    return dummy.next;
}

---

六、重要注意事项

1. 非线程安全
   多线程环境下需用 PriorityBlockingQueue 替代。
2. 迭代顺序不确定
   iterator() 遍历不保证有序，只有 poll()/peek() 能获取正确顺序。
3. 禁止 null 元素
   添加 null 会抛出 NullPointerException。
4. 动态扩容
   容量不足时自动扩容（每次约增长 50%），可能影响性能。
5. 对象排序要求：
   • 元素实现 Comparable 接口，或
   • 构造时传入 Comparator。

---

代码题高频使用技巧

场景	堆类型选择	关键操作
求最小 K 个数	大顶堆	当堆大小 > K 时 poll()
求最大 K 个数	小顶堆	当堆大小 > K 时 poll()
数据流中位数	大小顶堆组合	保持两堆大小差 ≤1
哈夫曼编码	小顶堆	反复合并最小两节点
定时任务调度	小顶堆（按时间戳排序）	peek() 检查最近任务

💡 经验法则：

• 需要快速访问最小值 → 小顶堆（默认）
• 需要快速访问最大值 → 大顶堆（Comparator.reverseOrder()）
• 遇到 "K个"、"最小/大"、"第K大" 关键词 → 优先考虑堆

---

总结

PriorityQueue 是算法题的核心数据结构，通过堆结构实现高效的最值访问。在解决 Top K、中位数、有序合并、最短路径 等问题时，能显著优化时间复杂度。关键点：

1. 默认小顶堆，大顶堆需自定义比较器
2. 插入/删除：O(log n)，访问队首：O(1)
3. 代码题中优先用于动态最值维护场景
4. 注意非线程安全和迭代无序的限制

通过合理选择堆类型和尺寸控制，可高效解决 80% 的堆相关算法题。