Java PriorityQueue高效使用技巧

答案：PriorityQueue是基于堆的优先级队列，默认为最小堆，用于高效获取极值，适用于任务调度、Top K等问题；它不保证全局有序，允许重复元素，添加和删除操作时间复杂度为O(log N)，但remove(Object)效率低，遍历时无序，需用poll()按序取出；自定义排序可通过Comparator实现，如最大堆或对象字段排序；注意初始容量设置、不可变排序字段、非线程安全及禁止null元素，与TreeSet相比更适用于仅关注极值的场景。

Java中的PriorityQueue，在我看来，它就是那个能帮你高效处理“谁最重要”这类问题的工具。它本质上是一个基于堆（heap）数据结构的优先级队列，默认情况下，它会帮你把最小的那个元素放在队头，让你能以非常快的速度拿到它。如果你需要一个总是能告诉你“当前最小（或最大）值是什么”的集合，并且你主要关心的是快速获取这个极值，而不是遍历整个集合的排序，那么PriorityQueue就是你的理想选择。它不是一个排序列表，而是一个为你维护优先级顺序的队列。

PriorityQueue的核心使用，其实围绕着几个基本操作展开，但理解它们背后的逻辑至关重要。

当你需要创建一个PriorityQueue时，通常有两种方式：

1. 默认最小堆： PriorityQueue minHeap = new PriorityQueue<>(); 这种情况下，它会根据元素的自然顺序（比如整数从小到大）来排序。
2. 自定义排序： PriorityQueue maxHeap = new PriorityQueue<>((s1, s2) -> s2.length() - s1.length()); 这里我们传入一个Comparator，决定了元素如何比较。比如，这个例子就是根据字符串长度从长到短排序，模拟一个最大堆。

往队列里添加元素，你可以用add()或offer()，它们的功能几乎一样，都是将元素插入到正确的位置，确保堆的性质得到维护。这个操作的时间复杂度是O(log N)，效率很高。

获取元素时，peek()会返回队头元素（也就是优先级最高的那个，默认是最小的），但不会将其移除。而poll()则会返回并移除队头元素。这两个操作也都是O(log N)。

一个常见的误解是，很多人以为PriorityQueue内部是完全排序的，比如你用迭代器去遍历它，会得到一个有序的序列。但实际上，这是不对的。PriorityQueue只保证队头元素是最小（或最大）的，内部其他元素的顺序只满足堆的性质，并不保证全局有序。如果你真的需要一个完全排序的集合，TreeSet可能更适合你。

PriorityQueue和TreeSet有什么区别，我什么时候该用它？

这个问题我经常被问到，它们俩确实有些相似之处，但核心用途大相径庭。简单来说，PriorityQueue是为了“快速找到并处理优先级最高的元素”而生的，而TreeSet则是为了“维护一个始终有序且不重复的集合”而存在。

PriorityQueue：

• 关注点： 极值（最小或最大）的快速存取。
• 内部结构： 堆（通常是二叉堆）。
• 元素重复： 允许重复元素。如果你添加两个相同的整数，它们都会在队列中。
• 迭代顺序： 不保证迭代器遍历时是完全有序的，只保证poll()出来的元素是有序的。
• 典型场景： 任务调度（优先级高的任务先执行）、Dijkstra算法（查找最短路径中的下一个节点）、Top K问题（找出最大或最小的K个元素）、模拟事件队列。

TreeSet：

• 关注点： 维护一个有序的、不重复的元素集合。
• 内部结构： 红黑树（一种自平衡二叉查找树）。
• 元素重复： 不允许重复元素。如果你添加一个已经存在的元素，它会被忽略。
• 迭代顺序： 迭代器遍历时，元素是严格按照自然顺序或自定义顺序排列的。
• 典型场景： 需要一个始终保持排序的集合、需要高效地进行范围查询（例如，找出所有大于X小于Y的元素）、维护唯一且有序的ID列表。

所以，如果你只是想快速拿到最小或最大的那个，并且不关心其他元素的全局排序，PriorityQueue是更高效的选择。但如果你需要一个随时都是有序的、且元素唯一的集合，甚至需要进行范围查询，那么TreeSet会更合适。举个例子，如果我要实现一个简单的任务调度器，每次都取出优先级最高的任务来执行，PriorityQueue就是我的首选。但如果我要维护一个用户在线列表，并且需要随时能按用户名排序显示，TreeSet就更合适。

如何自定义PriorityQueue的排序规则？

自定义PriorityQueue的排序规则，是它变得真正强大的地方。因为默认的自然排序很多时候并不能满足我们的需求。这主要通过在构造函数中传入一个Comparator来实现。

最常见的场景就是把默认的最小堆变成最大堆。比如，如果你想让整数从大到小排列：

// 方法一：匿名内部类（传统方式）
PriorityQueue maxHeapTraditional = new PriorityQueue<>(new Comparator() {
    @Override
    public int compare(Integer a, Integer b) {
        return b - a; // b - a 会让大的排在前面
    }
});

// 方法二：Lambda表达式（更简洁，Java 8+）
PriorityQueue maxHeapLambda = new PriorityQueue<>((a, b) -> b - a);

这两种方式都实现了同样的效果：让大的整数拥有更高的优先级（即排在队头）。

如果你要处理自定义对象，比如一个Task类，它有一个priority字段，你希望根据这个字段来排序：

class Task {
    String name;
    int priority; // 优先级，数字越小优先级越高

    public Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    public int getPriority() {
        return priority;
    }

    @Override
    public String toString() {
        return "Task{" + "name='" + name + '\'' + ", priority=" + priority + '}';
    }
}

// 根据Task的priority字段进行排序，priority值越小越优先（默认行为）
PriorityQueue taskQueue = new PriorityQueue<>(Comparator.comparingInt(Task::getPriority));

// 如果想让priority值越大越优先
PriorityQueue taskQueueReverse = new PriorityQueue<>(Comparator.comparingInt(Task::getPriority).reversed());

// 使用Lambda表达式直接比较
PriorityQueue customTaskQueue = new PriorityQueue<>((t1, t2) -> Integer.compare(t1.getPriority(), t2.getPriority()));

通过Comparator.comparingInt(Task::getPriority)这种方式，代码可读性会非常好。你也可以链式调用reversed()来反转排序顺序。

记住，如果你放入PriorityQueue的对象本身实现了Comparable接口，并且你没有提供Comparator，那么PriorityQueue会使用对象的自然顺序。但一旦你提供了Comparator，它就会覆盖对象的自然排序。这种灵活性使得PriorityQueue能够适应各种复杂的优先级需求。

PriorityQueue在使用中常见的性能陷阱和注意事项有哪些？

虽然PriorityQueue功能强大，但在实际使用中，如果不注意一些细节，可能会遇到性能问题或者逻辑错误。我个人在项目中就踩过几次坑，所以这些点特别值得强调。

1. remove(Object)的低效性： 这是个大坑。如果你需要从PriorityQueue中移除一个特定元素（而不是队头元素），remove(Object)方法的效率可能非常低。因为它需要遍历整个队列来找到那个元素（O(N)），然后重新调整堆结构（O(log N)），所以最坏情况下是O(N)或者O(N log N)。如果你经常需要移除非队头元素，可能需要重新考虑数据结构的选择，或者维护一个额外的Map来快速定位元素，但这会增加复杂性。

2. 迭代顺序不保证有序： 我之前提过，这里再强调一次。for-each循环遍历PriorityQueue时，元素的顺序是不确定的，它只是按照堆的内部结构来遍历，而不是按照优先级顺序。如果你需要按优先级顺序处理所有元素，正确的做法是反复调用poll()直到队列为空。

3. 初始容量的选择： PriorityQueue默认的初始容量是11。如果你的队列会存储大量元素，并且你知道大概的数量，最好在构造时就指定一个较大的初始容量，例如 new PriorityQueue<>(initialCapacity)。这样可以避免频繁的扩容操作，每次扩容都会涉及数组的复制，带来额外的性能开销。虽然Java的扩容机制相对高效，但能避免还是尽量避免。

4. 可变对象的陷阱： 如果你把自定义对象放入PriorityQueue，并且这些对象的某些字段是用于排序的（比如Task的priority），那么当这些字段在对象被添加到队列后发生改变时，PriorityQueue不会自动调整其内部结构。这意味着你的队列可能不再保持正确的优先级顺序。解决办法通常是，当对象的排序字段改变时，先从队列中remove()该对象，更新其字段，然后再add()回队列。这个操作虽然是O(N)的，但可以确保堆的正确性。

5. 非线程安全： PriorityQueue不是线程安全的。如果在多线程环境下使用，并且有多个线程同时对它进行修改（添加、移除），你需要手动进行同步，或者使用Java并发包中提供的PriorityBlockingQueue。PriorityBlockingQueue在内部已经处理了线程安全问题，但它在性能上会有一些开销。

6. 不允许null元素： PriorityQueue不允许存储null元素。如果你尝试添加null，它会抛出NullPointerException。这是因为null无法进行比较，也无法确定其优先级。

理解并规避这些潜在的问题，能让你更有效地利用PriorityQueue的优势，避免不必要的麻烦。在我看来，掌握这些细节，才是真正掌握一个工具的标志。