1. 概述
PriorityQueue 是 Java 中最强大的数据结构之一。虽然它在企业应用中不常见，但在算法实现和编程挑战中经常使用。
本教程将学习如何使用 Comparator 与 PriorityQueue 配合，以及如何改变队列的排序规则。 我们还会通过自定义类和 Pair 类的示例，展示类似逻辑的应用。
对于 Pair 类，我们将使用 Apache Commons 的实现。当然，还有多种选择，可根据需求选择最合适的方案。
2. PriorityQueue 基础
先聊聊这个数据结构本身。它的核心优势在于：插入元素时自动维护顺序。
但和其他队列一样，它不提供访问内部元素的 API。 我们只能访问队列头部的元素。
同时，它提供了几种移除元素的方法：removeAt() 和 removeEq()，也可以使用 AbstractCollection 的方法。虽然有用，但都不支持随机访问。
3. 排序机制
如前所述，PriorityQueue 的核心特性是维护元素顺序。与 LIFO/FIFO 不同，它的顺序与插入顺序无关。
因此我们需要明确队列的排序规则：要么元素实现 Comparable 接口，要么在创建队列时提供自定义 Comparator。
由于有两种方式，泛型参数不强制要求元素实现 Comparable。看这个类：
public class Book {
private final String author;
private final String title;
private final int publicationYear;
// 构造方法和 getter
}
用非可比较对象参数化队列不会报错：
@ParameterizedTest
@MethodSource("bookProvider")
void givenBooks_whenUsePriorityQueueWithoutComparatorWithoutAddingElements_thenNoExcetption(List<Book> books) {
PriorityQueue<Book> queue = new PriorityQueue<>();
assertThat(queue).isNotNull();
}
但尝试添加元素时，由于无法确定自然顺序，会抛出 ClassCastException：
@ParameterizedTest
@MethodSource("bookProvider")
void givenBooks_whenUsePriorityQueueWithoutComparator_thenThrowClassCastExcetption(List<Book> books) {
PriorityQueue<Book> queue = new PriorityQueue<>();
assertThatExceptionOfType(ClassCastException.class).isThrownBy(() -> queue.addAll(books));
}
这是常见处理方式，Collections.sort() 在排序非可比较元素时行为类似。注意：这不会产生编译时错误，容易踩坑。
4. Comparator 使用
如前所述，有两种方式定义队列顺序：实现 Comparable 接口，或在初始化时提供 Comparator。
4.1. Comparable 接口
当元素有自然顺序概念时，Comparable 接口很有用，无需为队列显式提供排序规则。 以 Meeting 类为例：
public class Meeting implements Comparable {
private final LocalDateTime startTime;
private final LocalDateTime endTime;
private final String title;
// 构造方法、getter、equals 和 hashCode
@Override
public int compareTo(Meeting meeting) {
return this.startTime.compareTo(meeting.startTime);
}
}
这里自然顺序是会议开始时间。 不同领域可能有不同定义，但足够说明问题。
直接使用 Meeting 类无需额外操作：
@Test
void givenMeetings_whenUseWithPriorityQueue_thenSortByStartDateTime() {
Meeting projectDiscussion = new Meeting(
LocalDateTime.parse("2025-11-10T19:00:00"),
LocalDateTime.parse("2025-11-10T20:00:00"),
"Project Discussion"
);
Meeting businessMeeting = new Meeting(
LocalDateTime.parse("2025-11-15T14:00:00"),
LocalDateTime.parse("2025-11-15T16:00:00"),
"Business Meeting"
);
PriorityQueue<Meeting> meetings = new PriorityQueue<>();
meetings.add(projectDiscussion);
meetings.add(businessMeeting);
assertThat(meetings.poll()).isEqualTo(projectDiscussion);
assertThat(meetings.poll()).isEqualTo(businessMeeting);
}
但如果需要偏离默认顺序，就得提供自定义 Comparator。
4.2. Comparator
创建 PriorityQueue 时，可以向构造函数传入 Comparator 定义排序规则。 以 Book 类为例（之前因未实现 Comparable 出问题）。
假设想按出版年份排序书单： 先读旧书以了解科幻思想发展脉络和早期作品的影响：
@ParameterizedTest
@MethodSource("bookProvider")
void givenBooks_whenUsePriorityQueue_thenSortThemBySecondElement(List<Book> books) {
PriorityQueue<Book> queue = new PriorityQueue<>(Comparator.comparingInt(Book::getPublicationYear));
queue.addAll(books);
Book previousBook = queue.poll();
while (!queue.isEmpty()) {
Book currentBook = queue.poll();
assertThat(previousBook.getPublicationYear())
.isLessThanOrEqualTo(currentBook.getPublicationYear());
previousBook = currentBook;
}
}
这里用方法引用创建按年份排序的比较器。添加书籍后，会优先取出旧书。
5. Pair 的使用
掌握自定义类示例后，在 PriorityQueue 中使用 Pair 就很简单了。本质上没有区别。假设 Pair 包含书名和出版年份：
@ParameterizedTest
@MethodSource("pairProvider")
void givenPairs_whenUsePriorityQueue_thenSortThemBySecondElement(List<Pair<String, Integer>> pairs) {
PriorityQueue<Pair<String, Integer>> queue = new PriorityQueue<>(Comparator.comparingInt(Pair::getSecond));
queue.addAll(pairs);
Pair<String, Integer> previousEntry = queue.poll();
while (!queue.isEmpty()) {
Pair<String, Integer> currentEntry = queue.poll();
assertThat(previousEntry.getSecond()).isLessThanOrEqualTo(currentEntry.getSecond());
previousEntry = currentEntry;
}
}
可见最后两个示例几乎完全相同。 唯一区别是 Comparator 操作 Pair 类。本例使用 Apache Commons 的 Pair 实现，但还有其他选择。
如果不想添加依赖，也可以用 Map.Entry：
@ParameterizedTest
@MethodSource("mapEntryProvider")
void givenMapEntries_whenUsePriorityQueue_thenSortThemBySecondElement(List<Map.Entry<String, Integer>> pairs) {
PriorityQueue<Map.Entry<String, Integer>> queue = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));
queue.addAll(pairs);
Map.Entry<String, Integer> previousEntry = queue.poll();
while (!queue.isEmpty()) {
Map.Entry<String, Integer> currentEntry = queue.poll();
assertThat(previousEntry.getValue()).isLessThanOrEqualTo(currentEntry.getValue());
previousEntry = currentEntry;
}
}
当然也可以自定义类表示 Pair。虽然能用数组或 List<Object>，但不推荐——这会破坏类型安全。
Pair 和 PriorityQueue 的组合在图遍历算法（如Dijkstra）中很常见。JavaScript/Python 能动态创建数据结构，而 Java 需要额外类/接口的初始设置。
6. 总结
PriorityQueue 是实现高性能简洁算法的利器。通过 Comparator 可定制排序规则，满足业务需求。
PriorityQueue 与 Pair 的结合能写出更健壮易读的代码。 但它属于进阶数据结构，不是所有开发者都熟悉其 API。
完整代码见 GitHub。