数据结构第27节 优先队列

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

Java中的PriorityQueue

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

主要特点：

1. 元素排序：PriorityQueue默认按照自然排序（自然顺序）来排序元素，即元素必须实现Comparable接口，或者在创建PriorityQueue时提供一个Comparator对象来定制排序规则。

2. 最小堆行为：PriorityQueue默认表现得像一个最小堆，即队列的头部元素是最小的元素。如果需要最大堆的行为，可以通过自定义比较器来实现。

3. 不允许null元素：PriorityQueue不允许插入null元素。

4. 不支持随机访问：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在不同应用场景下的使用方式。希望这些示例能够帮助你更好地理解优先队列在实际编程中的作用。