1. 基本概念
PriorityQueue 是 Java 集合框架中的一个基于优先堆的无界队列。它使用优先顺序（通常是元素的自然顺序或自定义比较器）来管理元素，而不是标准的 FIFO（先进先出）顺序。
// 基本创建方式 PriorityQueue<Integer> pq = new PriorityQueue<>(); // 最小堆（默认） PriorityQueue<Integer> pqMax = new PriorityQueue<>(Collections.reverseOrder()); // 最大堆2. 核心特性
| 特性 | 说明 |
|---|---|
| 排序方式 | 元素按优先级排序，队头总是优先级最高的元素 |
| 数据结构 | 基于二叉堆实现（默认最小堆） |
| 线程安全 | ❌不是线程安全的（如需线程安全用PriorityBlockingQueue） |
| null元素 | ❌ 不允许插入 null |
| 时间复杂度 | 插入/删除：O(log n)，获取队头：O(1) |
3. 常用操作示例
import java.util.PriorityQueue; public class PriorityQueueDemo { public static void main(String[] args) { // 1. 创建最小堆（默认） PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 添加元素 minHeap.offer(5); minHeap.offer(1); minHeap.offer(3); minHeap.offer(2); System.out.println("最小堆元素顺序："); while (!minHeap.isEmpty()) { System.out.print(minHeap.poll() + " "); // 输出: 1 2 3 5 } // 2. 创建最大堆 PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a); // 自定义比较器 maxHeap.offer(5); maxHeap.offer(1); maxHeap.offer(3); System.out.println("\n最大堆元素顺序："); while (!maxHeap.isEmpty()) { System.out.print(maxHeap.poll() + " "); // 输出: 5 3 1 } // 3. 自定义对象排序 PriorityQueue<Student> studentQueue = new PriorityQueue<>( (s1, s2) -> s1.score - s2.score // 按分数升序 ); } } class Student { String name; int score; // 构造方法等... }4. 底层实现原理
// 简化版内部结构理解 public class PriorityQueue<E> { private Object[] queue; // 存储元素的数组（二叉堆） private Comparator<? super E> comparator; // 添加元素时的上浮操作（heapify-up） // 删除元素时的下沉操作（heapify-down） }默认最小堆：父节点 ≤ 子节点
存储结构：数组实现的完全二叉树
父子节点关系：
父节点索引：
(i-1)/2左子节点：
2*i + 1右子节点：
2*i + 2
5. 典型应用场景
// 场景1：Top K 问题（找出最大的K个元素） public List<Integer> topK(int[] nums, int k) { PriorityQueue<Integer> minHeap = new PriorityQueue<>(); for (int num : nums) { minHeap.offer(num); if (minHeap.size() > k) { minHeap.poll(); // 移除最小的，保持K个最大的 } } return new ArrayList<>(minHeap); } // 场景2：合并多个有序列表 public ListNode mergeKLists(ListNode[] lists) { PriorityQueue<ListNode> pq = new PriorityQueue<>( (a, b) -> a.val - b.val ); // 将每个链表的头节点加入队列 // 每次弹出最小的，加入其下一个节点 } // 场景3：任务调度（按优先级执行） PriorityQueue<Task> taskQueue = new PriorityQueue<>( Comparator.comparingInt(Task::getPriority) );6. 注意事项
// ⚠️ 注意1：遍历时不保证顺序 PriorityQueue<Integer> pq = new PriorityQueue<>(); pq.add(3); pq.add(1); pq.add(2); System.out.println(pq); // 可能输出 [1, 3, 2] // 只有 poll() 或 peek() 才能看到正确顺序 // ⚠️ 注意2：不能插入不可比较对象 // PriorityQueue<Object> pq = new PriorityQueue<>(); // pq.add(new Object()); // 运行时错误：ClassCastException // ✅ 解决方案：提供Comparator PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>( Map.Entry.comparingByValue() );7. 与相关类的比较
| 类 | 排序方式 | 线程安全 | 边界 |
|---|---|---|---|
PriorityQueue | 优先级顺序 | ❌ 不安全 | 无界 |
ArrayDeque | FIFO/LIFO | ❌ 不安全 | 无界 |
LinkedList | 插入顺序 | ❌ 不安全 | 无界 |
PriorityBlockingQueue | 优先级顺序 | ✅ 安全 | 无界 |
总结
PriorityQueue适合需要动态排序且频繁访问最小/最大元素的场景
默认是最小堆，可通过 Comparator 改为最大堆或其他排序规则
是算法题中解决堆相关问题的常用工具（如 Top K、合并K个有序列表等）
注意其非线程安全特性，多线程环境下需要使用
PriorityBlockingQueue
