在Java中，`PriorityQueue` 是一个基于优先级堆的无界优先级队列。它不允许使用 `null` 元素，并且自然排序或者通过构造器提供的 `Comparator` 进行元素的排序。`PriorityQueue` 实现了 `java.util.Queue` 接口，但不是一个严格的先进先出（FIFO）队列，其元素按照指定的排序规则被移除。这种数据结构非常适合实现任务调度、优先级事件处理等场景。 ### PriorityQueue 的内部实现 `PriorityQueue` 实际上是通过一个基于数组的二叉堆来实现的。二叉堆是一种特殊的完全二叉树，其中每个父节点的值都大于或等于（最大堆）或小于或等于（最小堆）其子节点的值。Java中的 `PriorityQueue` 默认实现是一个最小堆，这意味着队列的头部（即 `peek()` 或 `poll()` 方法返回的元素）是当前队列中最小（或根据提供的 `Comparator` 排序后最小）的元素。 #### 二叉堆的数组表示 在二叉堆中，通常使用一维数组来存储堆的元素。给定数组中的某个位置 `i`，其父节点的位置是 `(i - 1) / 2`，左子节点的位置是 `2 * i + 1`，右子节点的位置是 `2 * i + 2`。这种简单的位置关系使得堆的操作（如插入、删除）变得高效。 #### 核心操作 1. **插入（`offer(E e)`）**： 向 `PriorityQueue` 插入一个新元素时，首先将新元素添加到数组的末尾，然后执行上浮（sift-up）操作，即将其与父节点比较，如果违反了堆的性质（对于最小堆，即新元素小于其父节点），则与父节点交换位置，继续这个过程直到新元素到达正确的位置。 2. **删除最小元素（`poll()`）**： 从 `PriorityQueue` 移除并返回队列中的最小元素时，通常移除的是数组的第一个元素（即堆顶元素），然后将数组的最后一个元素移动到堆顶，并执行下沉（sift-down）操作，即将新的堆顶元素与其子节点比较，如果违反了堆的性质，则与较小的子节点交换位置，直到它到达正确的位置。 3. **查找最小元素（`peek()`）**： 返回队列中的最小元素但不移除它。这只是一个简单的数组访问操作，返回数组的第一个元素（即堆顶元素）。 ### PriorityQueue 的构造函数 `PriorityQueue` 提供了几个构造函数来创建不同配置的优先队列： - `PriorityQueue()`：使用元素的自然顺序来创建一个空的优先队列。元素必须实现 `Comparable` 接口。 - `PriorityQueue(Collection c)`：根据给定集合元素的自然顺序创建一个优先队列。同样，元素必须实现 `Comparable` 接口。 - `PriorityQueue(int initialCapacity)`：创建一个空的优先队列，并指定其初始容量。 - `PriorityQueue(int initialCapacity, boolean naturalOrder)`：创建一个具有指定初始容量的空优先队列，并根据参数决定是否使用元素的自然顺序。 - `PriorityQueue(Comparator comparator)`：根据提供的 `Comparator` 创建一个空的优先队列。元素不需要实现 `Comparable` 接口。 - `PriorityQueue(Collection c, Comparator comparator)`：根据给定的集合和 `Comparator` 创建一个优先队列。 ### PriorityQueue 的使用示例 下面是一个使用 `PriorityQueue` 的简单示例，展示了如何创建一个最小堆，并向其中添加元素，然后移除并打印最小元素： ```java import java.util.PriorityQueue; public class PriorityQueueExample { public static void main(String[] args) { // 使用自然顺序创建一个PriorityQueue PriorityQueue pq = new PriorityQueue<>(); // 向队列中添加元素 pq.offer(10); pq.offer(1); pq.offer(5); pq.offer(20); // 移除并打印队列中的最小元素 while (!pq.isEmpty()) { System.out.println(pq.poll()); // 输出: 1, 5, 10, 20 } // 使用自定义比较器创建一个PriorityQueue PriorityQueue pqWithComparator = new PriorityQueue<>((s1, s2) -> s2.compareTo(s1)); // 向队列中添加字符串 pqWithComparator.offer("Java"); pqWithComparator.offer("Python"); pqWithComparator.offer("C++"); // 移除并打印队列中的最大元素（因为使用了反向比较器） while (!pqWithComparator.isEmpty()) { System.out.println(pqWithComparator.poll()); // 输出: C++, Python, Java } } } ``` ### PriorityQueue 的性能特点 - **插入操作**：时间复杂度为 O(log n)，其中 n 是队列中的元素数量。在最坏的情况下，新元素需要上浮到堆的顶部。 - **删除最小元素**：时间复杂度同样是 O(log n)，因为需要执行下沉操作来调整堆。 - **查找最小元素**：时间复杂度为 O(1)，因为它只是简单地返回堆顶元素。 ### 总结 `PriorityQueue` 是 Java 中的一个非常有用的数据结构，它利用二叉堆高效地实现了元素的优先排序。无论是自然排序还是通过自定义比较器排序，`PriorityQueue` 都提供了一种灵活且高效的方式来处理具有优先级的数据。在需要频繁进行插入和删除最小（或最大）元素的操作时，`PriorityQueue` 是一个很好的选择。通过码小课（一个专注于编程教育的网站），你可以深入学习更多关于 `PriorityQueue` 和其他 Java 数据结构的知识，进一步提升你的编程技能。