17370845950

Java中PriorityQueue是基于优先堆的无界队列，默认按自然升序排列，最小元素先出队，不支持null元素，入队和出队时间复杂度均为O(log n)。

Java中的PriorityQueue是一个基于优先堆的无界队列，它允许我们按照元素的优先级进行出队操作。默认情况下，PriorityQueue是按自然顺序（升序）排序的，也就是说最小的元素最先出队。它不支持null元素，并且入队和出队的时间复杂度为O(log n)。

基本使用方法

PriorityQueue实现了Queue接口，可以像普通队列一样使用offer()、poll()、peek()等方法。

• offer(E e)：将元素加入队列
• poll()：取出并移除队首元素（优先级最高）
• peek()：查看队首元素但不移除
• size()：返回队列大小

示例代码：

PriorityQueue pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
System.out.println(pq.peek()); // 输出 1
System.out.println(pq.poll()); // 输出 1
System.out.println(pq.poll()); // 输出 3

自定义排序规则

如果想改变默认排序方式，比如让大的元素优先级更高，可以通过传入Comparator来实现。

• 使用Lambda表达式或匿名内部类定义比较逻辑
• 例如实现降序排列

PriorityQueue pq = new PriorityQueue<>((a, b) -> b - a);
pq.offer(5);
pq.offer(1);
pq.offer(3);
System.out.println(pq.poll()); // 输出 5

对于自定义对象，比如Person类按年龄排序：

class Person {
    String name;
    int age;
    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
}
PriorityQueue pq = new PriorityQueue<>((p1, p2) -> p1.age - p2.age);
pq.offer(new Person("Alice", 30));
pq.offer(new Person("Bob", 20));
System.out.println(pq.poll().name); // 输出 Bob

常用场景与注意事项

PriorityQueue常用于需要动态维护最值的问题，比如Top K、合并K个有序链表、哈夫曼编码等。

• 不能保证相同优先级元素的顺序
• 不是线程安全的，多线程环境下应使用PriorityBlockingQueue
• 遍历时顺序不一定符合优先级顺序，应通过poll依次获取
• null元素不允许插入，否则抛出NullPointerException

基本上就这些。掌握构造、添加、取出和自定义排序就能应对大多数情况了。用起来不复杂，但容易忽略比较器的细节，特别是负数处理时建议用Integer.compare避免溢出。