PriorityQueue简介

一、总体概述

java.util.PriorityQueue<E> 基于最小堆 实现的可伸缩队列，符合队列 FIFO 的“取元素”语义，但优先级由比较器决定。它实现 Queue<E>、Serializable，默认小顶堆（最小值最高优先），可通过自定义 Comparator 变为最大堆或任意优先策略。

二、底层实现原理

三、复杂度分析

常数因子：比 TreeSet/TreeMap 更低（无额外指针、旋转），因此在仅需堆顶最值时更快。

四、完整 API 速查

五、注意事项 & 易错点

六、典型使用场景

七、线程安全方案

八、性能细节

1. 批量构造更快：new PriorityQueue<>(collection) 采用 Floyd 堆化，O(n)；逐个 add 为 O(nlogn)。
2. 最大堆技巧：PriorityQueue<Integer> max = new PriorityQueue<>((a,b)->b-a);。
3. 数组缓存：JDK17 开始 siftUp / siftDown 内联优化，实测百万级插入 ≈7–10M ops/s（取决于对象大小）。
4. 小顶堆变 K 小：当只关心 Top‑K 最大 元素时，用 固定容量最小堆，当大小>k 时 poll()。

九、示例代码

import java.util.*;  
  
public class PriorityQueueDemo {  
  
 // Top K 最大元素  
 static List<Integer> topK(int[] nums, int k) { PriorityQueue<Integer> minHeap = new PriorityQueue<>(k); // 小顶堆  
 for (int n : nums) { if (minHeap.size() < k) minHeap.offer(n); else if (n > minHeap.peek()) { minHeap.poll(); minHeap.offer(n); } } return new ArrayList<>(minHeap); // 未排序  
 }  
 // Dijkstra static int dijkstra(int n, List<int[]>[] g, int src, int dst) { int[] dist = new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] = 0; PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1])); pq.offer(new int[]{src, 0}); while (!pq.isEmpty()) { int[] cur = pq.poll(); int u = cur[0], d = cur[1]; if (u == dst) return d; if (d > dist[u]) continue; for (int[] e : g[u]) { int v = e[0], w = e[1]; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.offer(new int[]{v, dist[v]}); } } } return -1; }  
 public static void main(String[] args) { // Top‑K System.out.println(topK(new int[]{5, 2, 9, 1, 7, 6}, 3)); // [6,7,9]  
 // 最大堆示例  
 PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b)->b-a); maxHeap.addAll(Arrays.asList(4, 1, 7)); System.out.println(maxHeap.poll()); // 7 }}  

🔚 小结

• PriorityQueue = 最小（或自定义）堆 + 动态数组；
• 提供 O(logn) 的入队/出队，O(1) 查看堆顶；
• 适用于 Top‑K、Dijkstra、K 路归并、流式统计 等；
• 非线程安全，并发场景选 PriorityBlockingQueue 或外部加锁；
• 避免迭代器顺序误解、避免修改元素优先级后不重平衡、合理设置初始容量。