PriorityQueue底层基于最小堆(二叉堆)实现,使用动态扩容的Object数组,通过下标关系维护堆序,非红黑树;插入/删除为O(log n),不支持高效查找,遍历无序,需用poll()获取有序序列。
PriorityQueue底层用的是二叉堆,不是红黑树
Java的PriorityQueue默认基于**最小堆**(min-heap)实现,底层是动态扩容的Object数组,通过父/子节点下标关系(i → 2i+1、i → 2i+2)维护堆序,不是TreeSet那种红黑树结构。这意味着:
- 插入和删除时间复杂度都是
O(log n),但不支持O(log n)查找任意元素 - 遍历时(比如用
for (E e : pq))不保证按优先级顺序——它只保证poll()、peek()返回当前最高优先级元素 - 如果传入
Comparator,必须满足“不修改比较逻辑”的前提;若比较器在队列使用中动态变更,行为未定义
构造时指定Comparator要注意null安全和一致性
自定义优先级最常用方式是传Comparator,但容易踩两个坑:
- 若元素本身为
null,而Comparator没做判空(比如直接调用a.compareTo(b)),会抛NullPointerException - 比较逻辑必须满足自反性、传递性、对称性;例如用
Integer::compareTo比较int字段是对的,但用a > b ? 1 : -1漏掉a == b分支,会导致堆结构错乱 - 推荐写法:
Comparator.comparingInt(Task::priority).reversed()(最大堆)或(a, b) -> Integer.compare(a.priority, b.priority)
offer()和add()没区别,但poll()和element()异常行为不同
这两个方法语义差异直接影响错误处理策略: