什么是优先队列？Java 的 PriorityQueue 怎么用？

简化版

优先队列是一种队列，但出队的不是「最先进来的」，而是优先级最高的元素。它最常用二叉堆实现，插入和取出都是 O(log n)、看堆顶 O(1)。Java 的 PriorityQueue 就是堆实现，默认小顶堆（每次弹出最小值），传入 Comparator 可改成大顶堆或自定义优先级。

详细版

优先队列（Priority Queue） 的语义：每个元素有优先级，poll 时总是弹出优先级最高的（最大或最小，看定义）。

Java PriorityQueue 用法：

// 默认小顶堆：每次 poll 出最小值
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 大顶堆：传入逆序比较器
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// 或 new PriorityQueue<>((a, b) -> b - a);

// 自定义优先级：按对象某字段
PriorityQueue<Task> pq = new PriorityQueue<>((a, b) -> a.priority - b.priority);

minHeap.offer(5); minHeap.offer(1); minHeap.offer(3);
minHeap.peek();   // 1（看堆顶，不删）O(1)
minHeap.poll();   // 1（弹出最小）O(log n)

操作	方法	复杂度
入队	`offer(x)` / `add(x)`	O(log n)
出队（取最值）	`poll()`	O(log n)
看堆顶	`peek()`	O(1)
建堆（传集合）	`new PriorityQueue<>(coll)`	O(n)

完整版教学

一、优先队列 vs 普通队列

普通队列：FIFO，先进先出，出队顺序 = 入队顺序。
优先队列：出队顺序 = 优先级顺序，和入队顺序无关。谁优先级高谁先出。

优先队列是「队列」这个名字下的一个抽象概念，核心是「总能高效拿到当前最重要的元素」。它的实现可以是有序数组（插入 O(n)）、有序链表等，但堆是综合最优的实现（插入、取最值都是 O(log n)），所以几乎所有优先队列都用堆。

二、Java PriorityQueue 的关键点

默认小顶堆：不传比较器时，按自然顺序（Comparable），堆顶是最小值，poll 弹出最小。这点常被记错——很多人以为默认是大顶堆。
改成大顶堆：传 Collections.reverseOrder() 或 (a,b) -> b-a（注意用 b-a 可能整数溢出，稳妥用 Integer.compare(b,a)）。
自定义优先级：传 Comparator，按对象的某个字段排。
底层是数组实现的二叉堆，动态扩容。

三、几个使用注意

不允许 null：offer(null) 抛 NullPointerException。
不是线程安全：并发要用 PriorityBlockingQueue。
遍历无序：PriorityQueue 的迭代器/toArray 不保证有序——它只保证 poll 有序。想有序输出得反复 poll。这是常见误区。
比较器要自洽：自定义 Comparator 要满足全序，否则行为未定义。

四、比较器溢出陷阱

用 (a, b) -> a - b 做比较器时，如果 a、b 是很大的正负整数，a - b 可能溢出导致比较错误。稳妥写法是用 Integer.compare(a, b)：

// 有溢出风险：
new PriorityQueue<>((a, b) -> a - b);
// 安全：
new PriorityQueue<>((a, b) -> Integer.compare(a, b));

五、典型应用

优先队列是很多算法的核心组件：

Top K / 第 K 大：维护 size K 的堆。
合并 K 个有序链表/数组：小顶堆存各路当前最小。
Dijkstra 最短路 / Prim 最小生成树：每次取当前距离最小的节点。
任务调度 / 定时器 / 延迟队列：按到期时间取最早的任务（Java DelayQueue）。
哈夫曼编码：反复取两个频率最小的节点合并。

六、常见误区与追问

考点	正确口径
普通队列	先入先出
优先队列	每次弹出优先级最高元素
Java PriorityQueue	默认小顶堆，按自然顺序或 Comparator

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(3); pq.offer(1); pq.offer(2);
pq.poll(); // 1

PriorityQueue 的队头是最小元素或比较器定义的最高优先级元素，不是最早入队元素。

误区：PriorityQueue 遍历结果是有序的。 迭代器不保证有序；只有连续 poll 才会按优先级输出。
误区：Java PriorityQueue 默认是大顶堆。 Java 默认是小顶堆；大顶堆需要自定义比较器。
误区：比较器写成 b - a 永远安全。 整数极值相减可能溢出，建议使用 Integer.compare(b, a)。
追问：PriorityQueue 能放 null 吗？ Java PriorityQueue 不允许 null，因为需要比较和区分空返回。
追问：删除任意元素复杂度如何？ 按对象删除需要线性查找，通常是 O(n)，不是堆的强项。
追问：线程安全吗？ PriorityQueue 不是线程安全的，多线程需要外部同步或使用 PriorityBlockingQueue。

七、加强记忆

优先队列 = 出队时弹出优先级最高（而非最先进入）的队列，最常用堆实现（插入/取最值 O(log n)、peek O(1)）。Java PriorityQueue 是堆，默认小顶堆（poll 出最小），传 Comparator/reverseOrder 改大顶堆或自定义。注意：遍历无序（只有 poll 有序）、不能存 null、非线程安全（并发用 PriorityBlockingQueue）、比较器用 Integer.compare 防溢出。

简化版

详细版