数据结构第27节优先队列

优先队列（Priority Queue）是在计算机科学中一种非常有用的抽象数据类型，它与标准队列的主要区别在于元素的出队顺序不是先进先出（FIFO），而是基于每个元素的优先级。具有较高优先级的元素会比低优先级的元素更早出队。在Java中，PriorityQueue类是实现优先队列的一种方式。

Java中的`PriorityQueue`

java.util.PriorityQueue是Java集合框架的一部分，它实现了Queue接口。PriorityQueue底层使用了一个名为堆的数据结构，通常是一个二叉堆，以保证每次操作的时间复杂度为O(log n)，其中n是队列中的元素数量。

主要特点：

元素排序：PriorityQueue默认按照自然排序（自然顺序）来排序元素，即元素必须实现Comparable接口，或者在创建PriorityQueue时提供一个Comparator对象来定制排序规则。
最小堆行为：PriorityQueue默认表现得像一个最小堆，即队列的头部元素是最小的元素。如果需要最大堆的行为，可以通过自定义比较器来实现。
不允许null元素：PriorityQueue不允许插入null元素。
不支持随机访问：PriorityQueue不支持快速随机访问元素，因为它不是基于索引的结构。

常用方法：

add(E e)：将指定的元素添加到此队列中。
offer(E e)：如果可能立即添加指定的元素而不会违反队列的容量限制，则添加；否则返回false。
remove()：检索并移除此队列的头；如果此队列为空，则抛出NoSuchElementException异常。
poll()：检索并移除此队列的头；如果此队列为空，则返回null。
peek()：检索但不移除此队列的头；如果此队列为空，则返回null。
size()：返回队列中的元素个数。
isEmpty()：如果队列中没有元素，则返回true。

示例代码：

下面是一个使用PriorityQueue的例子，展示如何创建和使用一个优先队列：

import java.util.PriorityQueue;
import java.util.Comparator;public class PriorityQueueExample {public static void main(String[] args) {// 创建一个基于数字大小的优先队列PriorityQueue<Integer> pq = new PriorityQueue<>();// 添加元素pq.add(5);pq.add(1);pq.add(3);// 输出队列头部的元素System.out.println("Head element: " + pq.peek()); // 输出最小的元素，这里是1// 移除并输出队列头部的元素System.out.println("Removed head element: " + pq.remove()); // 输出并移除最小的元素，这里是1// 使用自定义比较器创建优先队列PriorityQueue<String> pqStrings = new PriorityQueue<>(new Comparator<String>() {@Overridepublic int compare(String s1, String s2) {return s2.compareTo(s1); // 反转字符串的排序顺序}});// 添加字符串元素pqStrings.add("Apple");pqStrings.add("Banana");pqStrings.add("Cherry");// 输出队列头部的元素System.out.println("Head element: " + pqStrings.peek()); // 输出最大的元素，这里是"Cherry"}
}

在这个例子中，我们创建了两个PriorityQueue实例。第一个实例是基于整数的优先队列，按照数字大小排序。第二个实例是基于字符串的优先队列，使用自定义的比较器来反转字符串的自然排序顺序。

优先队列在很多场景下都非常有用，比如任务调度、事件驱动模拟、Dijkstra算法中的最短路径计算、以及各种基于优先级的系统中。

下面我会给出几个具体的场景以及相应的Java代码实现，以便你了解优先队列在实际编程中的应用方式。

场景1：任务调度

在任务调度场景中，优先级高的任务会被优先执行。这里我们使用PriorityQueue来管理任务列表。

import java.util.PriorityQueue;class Task implements Comparable<Task> {private String name;private int priority;public Task(String name, int priority) {this.name = name;this.priority = priority;}public String getName() {return name;}public int getPriority() {return priority;}@Overridepublic int compareTo(Task other) {return Integer.compare(this.priority, other.priority);}
}public class TaskScheduler {private PriorityQueue<Task> tasks = new PriorityQueue<>();public void addTask(Task task) {tasks.add(task);}public Task getNextTask() {return tasks.poll();}public static void main(String[] args) {TaskScheduler scheduler = new TaskScheduler();scheduler.addTask(new Task("Task1", 3));scheduler.addTask(new Task("Task2", 1));scheduler.addTask(new Task("Task3", 2));while (!scheduler.tasks.isEmpty()) {Task task = scheduler.getNextTask();System.out.println("Executing: " + task.getName());}}
}

场景2：Dijkstra算法

Dijkstra算法用于在加权图中寻找两个顶点之间的最短路径。优先队列在这里用来保存待访问的顶点，按照它们的当前最小距离排序。

import java.util.*;public class DijkstraAlgorithm {private Map<String, List<Edge>> graph = new HashMap<>();private Map<String, Integer> distances = new HashMap<>();private PriorityQueue<Edge> queue = new PriorityQueue<>();public void addEdge(String source, String destination, int weight) {graph.computeIfAbsent(source, k -> new ArrayList<>()).add(new Edge(destination, weight));}public void calculateShortestPaths(String startVertex) {distances.put(startVertex, 0);queue.add(new Edge(startVertex, 0));while (!queue.isEmpty()) {Edge edge = queue.poll();String vertex = edge.getDestination();if (distances.containsKey(vertex)) continue; // Already processeddistances.put(vertex, edge.getWeight());for (Edge neighbor : graph.getOrDefault(vertex, Collections.emptyList())) {queue.add(new Edge(neighbor.getDestination(), distances.get(vertex) + neighbor.getWeight()));}}}public static void main(String[] args) {DijkstraAlgorithm dijkstra = new DijkstraAlgorithm();dijkstra.addEdge("A", "B", 5);dijkstra.addEdge("A", "C", 10);dijkstra.addEdge("B", "D", 3);dijkstra.addEdge("C", "D", 1);dijkstra.addEdge("C", "E", 2);dijkstra.addEdge("D", "E", 1);dijkstra.addEdge("D", "F", 5);dijkstra.addEdge("E", "F", 5);dijkstra.calculateShortestPaths("A");System.out.println(dijkstra.distances);}static class Edge implements Comparable<Edge> {private String destination;private int weight;public Edge(String destination, int weight) {this.destination = destination;this.weight = weight;}public String getDestination() {return destination;}public int getWeight() {return weight;}@Overridepublic int compareTo(Edge other) {return Integer.compare(this.weight, other.weight);}}
}

场景3：事件驱动的模拟

在事件驱动的模拟中，事件按照发生的时间排序。优先队列可以用来保持事件列表的有序性。

import java.util.PriorityQueue;class Event implements Comparable<Event> {private long time;private String description;public Event(long time, String description) {this.time = time;this.description = description;}public long getTime() {return time;}public String getDescription() {return description;}@Overridepublic int compareTo(Event other) {return Long.compare(this.time, other.time);}
}public class EventDrivenSimulation {private PriorityQueue<Event> events = new PriorityQueue<>();public void scheduleEvent(long time, String description) {events.add(new Event(time, description));}public void runSimulation() {while (!events.isEmpty()) {Event event = events.poll();System.out.println("Time: " + event.getTime() + ", Event: " + event.getDescription());}}public static void main(String[] args) {EventDrivenSimulation simulation = new EventDrivenSimulation();simulation.scheduleEvent(1000, "Start");simulation.scheduleEvent(1010, "Event 1");simulation.scheduleEvent(1005, "Event 2");simulation.runSimulation();}
}