阅读量:0
优先队列（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>() { @Override public 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; } @Override public 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 processed distances.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; } @Override public 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; } @Override public 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(); } } 在上述代码中，我们创建了三个不同的场景，每个场景都展示了PriorityQueue在不同应用场景下的使用方式。希望这些示例能够帮助你更好地理解优先队列在实际编程中的作用。
