Java集合框架中的PriorityQueue使用场景

PriorityQueue适合解决需动态获取最小（或最大）元素的问题，如任务调度、Top-K查询、合并K个有序链表、Dijkstra算法中的节点选择等。

PriorityQueue适合解决哪些实际问题

PriorityQueue不是为“按插入顺序遍历”设计的，而是专用于需要动态获取最小（或最大）元素的场景。它背后是堆结构，offer、poll、peek 的平均时间复杂度都是 O(log n)，比每次遍历找最小值的 O(n) 高效得多。

典型使用场景包括：

• 任务调度系统中按优先级执行任务（如紧急任务优先）
• Top-K 问题：比如实时热搜榜取前10、日志中找访问量最高的5个IP
• 合并K个有序链表（LeetCode 23）
• Dijkstra最短路径算法中的“当前距离最小的未访问节点”选择

如何正确设置最大堆或最小堆

Java的PriorityQueue默认是最小堆——即poll()返回最小元素。想实现最大堆，不能靠“反转比较逻辑”这种直觉操作，必须显式传入Comparator。

常见错误写法：new PriorityQueue((a, b) -> b - a) —— 这在a、b为大整数时可能溢出，导致排序异常。

推荐写法：

new PriorityQueue(Comparator.reverseOrder())

或者对自定义类：

new PriorityQueue(Comparator.comparing(p -> p.age).reversed())

注意：PriorityQueue不保证全部元素有序，只保证队首满足堆性质；遍历时（如用for (E e : pq)）顺序无意义，不能用来“取前N

个最大值”。

PriorityQueue和TreeSet/TreeMap的关键区别

三者都支持排序，但语义完全不同：

• PriorityQueue允许重复元素，不提供contains高效查找（O(n)），也不支持删除中间元素（只有remove(Object)，但内部需线性扫描）
• TreeSet去重、支持O(log n)查找与删除任意元素，但没有“只关心最小/最大”的优化接口
• 如果业务既要频繁取极值，又要支持按值删除或存在性判断，PriorityQueue就不是最佳选择——此时应考虑配合HashMap做懒删除，或直接换用TreeSet

例如实现带删除的Top-K流处理，常见模式是：

PriorityQueue heap = new PriorityQueue<>();
Map delayedRemoval = new HashMap<>(); // value → count

每次poll()前先检查堆顶是否已被标记删除。

线程安全问题与替代方案

PriorityQueue本身不是线程安全的。多线程环境下直接共享一个实例，调用offer()和poll()可能引发ConcurrentModificationException或数据丢失。

不要试图用Collections.synchronizedCollection(new PriorityQueue())——它只同步单个方法，无法保证复合操作（如if (!pq.isEmpty()) pq.poll()）的原子性。

真正需要并发优先队列时，应选用：

• PriorityBlockingQueue：无界、线程安全、不支持null，适合生产者-消费者模型
• 若需有界+阻塞+优先级，可封装ReentrantLock + Condition + PriorityQueue，但复杂度高，慎选

很多场景下，所谓“并发优先队列需求”，其实只是误判了并发粒度——把锁范围缩小到业务单元（如每个用户独立队列），比全局共享一个PriorityQueue更简单可靠。