Java优先队列原理与堆结构详解

从现在开始，我们要努力学习啦！今天我给大家带来《Java优先队列实现原理及堆结构解析》，感兴趣的朋友请继续看下去吧！下文中的内容我们主要会涉及到等等知识点，如果在阅读本文过程中有遇到不清楚的地方，欢迎留言呀！我们一起讨论，一起学习！

PriorityQueue 默认基于小顶堆实现，不保证数组有序，仅维护堆性质；offer/poll 时间复杂度为 O(log n)，peek 为 O(1)；自定义排序需用 Comparator 或 Comparable；不支持元素修改后自动重排序。

PriorityQueue 在 Java 中默认按自然顺序排序，底层用的是小顶堆（最小堆），不是直接排序，而是通过堆结构维护“每次 poll() 都能拿到当前优先级最高（即最小）的元素”这一特性。

底层是小顶堆，不是数组直接排序

PriorityQueue 内部使用动态扩容的 Object[] 数组存储元素，但不保证整个数组有序。它只维持堆性质：对任意索引 i，都有 queue[i] ≤ queue[2i+1] 且 queue[i] ≤ queue[2i+2]（左、右子节点都不小于父节点）。所以你遍历数组看到的顺序，不是逻辑上的优先级顺序。

• 添加元素（offer）：先加到末尾，再向上调整（siftUp），直到满足堆序
• 取出头元素（poll）：把堆顶和末尾交换，删掉末尾，再对新堆顶向下调整（siftDown）
• 时间复杂度：offer 和 poll 都是 O(log n)，peek 是 O(1)

如何自定义优先级？靠 Comparator 或 Comparable

默认情况下，元素必须实现 Comparable 接口（如 Integer、String），否则运行时报 ClassCastException。想按其他规则排，就传 Comparator：

• 升序（默认）：new PriorityQueue<>() 或 new PriorityQueue<>(Comparator.naturalOrder())
• 降序：new PriorityQueue<>(Comparator.reverseOrder())
• 按字符串长度：new PriorityQueue<>((a, b) → a.length() - b.length())
• 多条件：先比分数，分数相同再比姓名字典序 (a, b) → { int d = b.score - a.score; return d != 0 ? d : a.name.compareTo(b.name); }

注意：修改队列中已存在元素不会自动重排序

PriorityQueue 不监听元素内部状态变化。比如你往队里放了一个 Person 对象，之后改了它的 score 字段，队列不会重新调整位置。

• 正确做法：先 remove() 再重新 offer()（remove 是 O(n)，慎用）
• 更优方案：避免中途修改；或用支持更新的结构（如 TreeSet + 自定义逻辑，或第三方库如 Apache Commons PriorityQueue）
• 另外，contains() 和 remove(Object) 都要遍历查找，效率不高，不适合高频查找场景

常见误区与提醒

• PriorityQueue 不是线程安全的，多线程要用 PriorityBlockingQueue
• null 元素不允许（除非用 null-safe 的 Comparator，但也不推荐）
• 不能用 for-each 遍历获取“已排序结果”，那只是数组物理顺序，不是逻辑顺序；真要全排序，得反复 poll() 或转成数组后 Arrays.sort()
• 初始容量可指定，避免频繁扩容；但即使设了容量，也只影响底层数组大小，不影响堆逻辑

基本上就这些。理解它是“堆”而不是“排序列表”，就能避开大多数坑。

好了，本文到此结束，带大家了解了《Java优先队列原理与堆结构详解》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！