4. 什么是优先队列（Priority Queue）？如何在Java中使用PriorityQueue实现它？
大约 5 分钟
1. 什么是优先队列（Priority Queue）？
优先队列（Priority Queue） 是一种特殊的队列数据结构，它与普通的队列不同，普通队列是按照“先进先出”（FIFO, First-In-First-Out）的原则来处理元素的，而优先队列中的元素是按照优先级进行排序的，每次出队操作都是取出优先级最高的元素（最小或最大）。
优先队列的常见操作包括：
- 插入元素：元素会被插入到队列中，并根据优先级进行排序。
- 取出元素：每次取出的元素都是优先级最高的元素。
优先队列通常使用堆（Heap）这种数据结构来实现，这使得插入和删除操作的时间复杂度为 O(log n)。
2. 在 Java 中使用 PriorityQueue 实现优先队列
Java 提供了 PriorityQueue 类来实现优先队列。PriorityQueue 默认是一个最小堆，也就是说，队首元素是优先级最小的元素。
2.1 使用 PriorityQueue 的基本操作
示例代码：
import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
// 创建一个 PriorityQueue
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
// 向队列中插入元素
priorityQueue.offer(5);
priorityQueue.offer(1);
priorityQueue.offer(3);
priorityQueue.offer(10);
// 打印 PriorityQueue
System.out.println("PriorityQueue: " + priorityQueue);
// 获取并移除优先级最高的元素（最小的元素）
System.out.println("Polled element: " + priorityQueue.poll());
// 获取队首元素但不移除
System.out.println("Peeked element: " + priorityQueue.peek());
// 再次打印 PriorityQueue
System.out.println("PriorityQueue after polling: " + priorityQueue);
}
}说明：
offer()方法用于向优先队列中插入元素，插入的元素会根据其自然顺序（或自定义的顺序）自动排列。poll()方法用于取出并移除优先级最高的元素，即最小的元素。peek()方法用于获取队首元素但不移除它。
输出示例：
PriorityQueue: [1, 5, 3, 10]
Polled element: 1
Peeked element: 3
PriorityQueue after polling: [3, 5, 10]2.2 自定义对象的优先级排序
如果需要在 PriorityQueue 中存储自定义对象，通常需要实现 Comparable 接口或传入一个 Comparator 来定义排序规则。
示例代码：
import java.util.PriorityQueue;
import java.util.Comparator;
class Task implements Comparable<Task> {
private String name;
private int priority;
public Task(String name, int priority) {
this.name = name;
this.priority = priority;
}
public int getPriority() {
return priority;
}
@Override
public int compareTo(Task other) {
return Integer.compare(this.priority, other.priority);
}
@Override
public String toString() {
return "Task{" +
"name='" + name + '\'' +
", priority=" + priority +
'}';
}
}
public class CustomPriorityQueueExample {
public static void main(String[] args) {
// 创建一个 PriorityQueue
PriorityQueue<Task> taskQueue = new PriorityQueue<>();
// 向队列中插入元素
taskQueue.offer(new Task("Task 1", 5));
taskQueue.offer(new Task("Task 2", 1));
taskQueue.offer(new Task("Task 3", 3));
taskQueue.offer(new Task("Task 4", 2));
// 打印 PriorityQueue
System.out.println("Task Queue: " + taskQueue);
// 获取并移除优先级最高的任务
System.out.println("Polled task: " + taskQueue.poll());
// 再次打印 PriorityQueue
System.out.println("Task Queue after polling: " + taskQueue);
}
}说明：
Task类实现了Comparable<Task>接口，compareTo方法用于定义任务的优先级比较规则。PriorityQueue会根据compareTo方法的返回值对Task对象进行排序。
输出示例：
Task Queue: [Task{name='Task 2', priority=1}, Task{name='Task 4', priority=2}, Task{name='Task 3', priority=3}, Task{name='Task 1', priority=5}]
Polled task: Task{name='Task 2', priority=1}
Task Queue after polling: [Task{name='Task 4', priority=2}, Task{name='Task 1', priority=5}, Task{name='Task 3', priority=3}]2.3 自定义 Comparator 实现不同的排序规则
如果不想在类中实现 Comparable 接口，还可以使用 Comparator 在创建 PriorityQueue 时自定义排序规则。
示例代码：
import java.util.PriorityQueue;
import java.util.Comparator;
class Task {
private String name;
private 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 +
'}';
}
}
public class CustomComparatorExample {
public static void main(String[] args) {
// 使用自定义 Comparator 创建一个 PriorityQueue
PriorityQueue<Task> taskQueue = new PriorityQueue<>(Comparator.comparingInt(Task::getPriority).reversed());
// 向队列中插入元素
taskQueue.offer(new Task("Task 1", 5));
taskQueue.offer(new Task("Task 2", 1));
taskQueue.offer(new Task("Task 3", 3));
taskQueue.offer(new Task("Task 4", 2));
// 打印 PriorityQueue
System.out.println("Task Queue: " + taskQueue);
// 获取并移除优先级最高的任务
System.out.println("Polled task: " + taskQueue.poll());
// 再次打印 PriorityQueue
System.out.println("Task Queue after polling: " + taskQueue);
}
}说明：
Comparator.comparingInt(Task::getPriority).reversed()定义了一个自定义的排序规则，使得优先级最高的任务（优先级值最大）排在队首。PriorityQueue使用这个Comparator对任务进行排序。
输出示例：
Task Queue: [Task{name='Task 1', priority=5}, Task{name='Task 4', priority=2}, Task{name='Task 3', priority=3}, Task{name='Task 2', priority=1}]
Polled task: Task{name='Task 1', priority=5}
Task Queue after polling: [Task{name='Task 3', priority=3}, Task{name='Task 4', priority=2}, Task{name='Task 2', priority=1}]3. PriorityQueue 的应用场景
优先队列在许多实际应用中非常有用，以下是一些常见的应用场景：
- 任务调度系统：在任务调度系统中，优先队列可以用来管理任务的执行顺序，确保优先级高的任务先执行。
- 路径搜索算法：在图的搜索算法（如 Dijkstra 算法）中，优先队列用来选取当前权重最小的路径进行扩展。
- 事件驱动系统：在事件驱动的模拟系统中，优先队列可以用来管理和处理按时间排序的事件。
4. 总结
优先队列是一种重要的数据结构，能够根据元素的优先级进行排序和管理。Java 提供了 PriorityQueue 类来实现优先队列，通过堆（最小堆或最大堆）的方式来保证每次出队操作都能获取优先级最高的元素。对于自定义对象，PriorityQueue 支持使用 Comparable 接口或 Comparator 来定义排序规则。根据实际需求，可以选择合适的优先队列实现方式来优化系统的性能和逻辑处理。