Java集合框架中的PriorityQueue与集合排序_技术教程

PriorityQueue 底层基于堆实现，仅保证队首元素最小（或最大），不维护整体有序性；遍历顺序不可预测，正确使用方式仅为 poll()、peek()、offer()；适合动态获取极值场景，非静态排序需求。

PriorityQueue 不是排序集合，它只保证队首最小（或最大）

很多人误以为 PriorityQueue 是一个“自动排序的 List”，实际它底层是基于堆（heap）实现的，不维护整体有序性。遍历 PriorityQueue 时，元素顺序完全不可预测——iterator() 不按优先级顺序返回，toString() 输出也看不出逻辑顺序。

真正有效的访问方式只有：poll()、peek()、offer()。每次 poll() 才会弹出当前优先级最高（默认最小）的元素，并重新调整堆结构。

不要用 for (E e : pq) 试图“读取已排序数据”
不要把 PriorityQueue 当作替代 TreeSet 或 “排序后转 List” 的捷径
如果需要完整有序序列，必须反复 poll() 直到为空，或先转数组再用 Arrays.sort()

Comparator 决定优先级，但不影响底层存储布局

PriorityQueue 的排序行为完全由构造时传入的 Comparator（或元素自然序）控制，但它不会重排已有元素——插入和删除才触发堆化（heapify）。

例如：你往空队列中依次 offer(3)、offer(1)、offer(2)，内部数组可能是 [1, 3, 2]（满足最小堆性质），但绝不是 [1, 2, 3] 这样的升序排列。

自定义 Comparator 必须
保持一致性：对同一对元素多次比较结果不能变
若元素可变且影响比较字段，修改后未重新 offer()，会导致堆逻辑损坏
使用 Comparator.reverseOrder() 可快速构建最大堆，无需重写逻辑

想获得排序后的集合？别依赖 PriorityQueue 的遍历

如果你的目标只是“把一批数据排好序”，PriorityQueue 是过度设计。直接用 Collections.sort() 或流式处理更清晰、更高效：

List list = Arrays.asList(3, 1, 4, 1, 5);
Collections.sort(list); // 升序
// 或
list.stream().sorted().collect(Collectors.toList());

而用 PriorityQueue 强行“排序”反而绕路：

PriorityQueue pq = new PriorityQueue<>(list);
List sorted = new ArrayList<>();
while (!pq.isEmpty()) {
    sorted.add(pq.poll()); // 正确方式，但比 Collections.sort() 多 O(n log n) 堆操作开销
}

Collections.sort() 对随机访问列表是双轴快排，平均性能更好
PriorityQueue 适合动态增删 + 持续获取极值的场景（如 Top-K、任务调度）
临时排序需求 + 静态数据 → 别碰 PriorityQueue

和 TreeSet 的关键区别：重复元素与性能边界

TreeSet 也支持排序和 O(log n) 插入/查找，但它去重、支持 floor()/ceiling()，且遍历时严格有序；PriorityQueue 允许重复、无查找能力、遍历无序。

需要查某个值是否存在？用 TreeSet，别用 PriorityQueue.contains()（它是 O(n)）
要保留重复元素并只关心最小值？PriorityQueue 更轻量
频繁调用 size() 或 isEmpty() 两者都快；但频繁 remove(Object) 在 PriorityQueue 中是 O(n)，TreeSet 是 O(log n)