### PriorityQueue 的特性和原理 `PriorityQueue` 是基于堆（heap）实现的优先级队列，通常是最小堆（即堆顶元素是最小值）。队列中的元素按照自然顺序或通过提供的比较器进行排序。 #### 主要特性 * **基于堆数据结构**：一般使用最小堆。 * **无界队列**：可以动态扩容。 * **元素排序**：按照自然顺序或通过自定义的比较器排序。 * **线程不安全**：不适用于多线程环境，需要手动同步。 ### PriorityQueue 的核心实现及源码分析 #### 1\. 数据结构 `PriorityQueue` 的核心数据结构是一个动态数组，用于存储堆中的元素。 ~~~ java复制代码public class PriorityQueue<E> extends AbstractQueue<E> implements java.io.Serializable { private static final int DEFAULT_INITIAL_CAPACITY = 11; // 默认初始容量 transient Object[] queue; // 用于存储元素的数组 private int size = 0; // 当前元素数量 private final Comparator<? super E> comparator; // 自定义比较器（可选） // 构造函数和其他方法省略... } ~~~ * `queue`: 动态数组，用于存储堆中的元素。 * `size`: 当前队列中的元素数量。 * `comparator`: 自定义的比较器（可选），用于定义元素的排序规则。 #### 2\. 插入元素 `offer` 方法用于插入元素，内部调用 `add` 方法。 ~~~ java复制代码public boolean add(E e) { return offer(e); } public boolean offer(E e) { if (e == null) throw new NullPointerException(); // 检查空值 modCount++; int i = size; if (i >= queue.length) // 如果数组已满，进行扩容 grow(i + 1); size = i + 1; if (i == 0) queue[0] = e; // 第一个元素直接放入 else siftUp(i, e); // 其他元素进行堆调整 return true; } private void grow(int minCapacity) { int oldCapacity = queue.length; // 扩容策略：当容量小于 64 时，每次扩容为原来的两倍；当容量大于等于 64 时，每次扩容为原来的 1.5 倍 int newCapacity = oldCapacity + (oldCapacity < 64 ? (oldCapacity + 2) : (oldCapacity >> 1)); if (newCapacity - Integer.MAX_VALUE > 0) newCapacity = hugeCapacity(minCapacity); queue = Arrays.copyOf(queue, newCapacity); // 扩容并复制元素到新数组 } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // 溢出 throw new OutOfMemoryError(); return (minCapacity > Integer.MAX_VALUE) ? Integer.MAX_VALUE : Integer.MAX_VALUE; } ~~~ * **空值检查**：不允许插入 null 值。 * **扩容检查**：如果当前数组已满，则进行扩容。 * **插入元素**：将元素插入到数组末尾，然后通过 `siftUp` 方法进行堆调整。 `SiftUp` 方法： ~~~ java复制代码private void siftUp(int k, E x) { if (comparator != null) siftUpUsingComparator(k, x); else siftUpComparable(k, x); } private void siftUpComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>) x; while (k > 0) { int parent = (k - 1) >>> 1; // 计算父节点索引 Object e = queue[parent]; if (key.compareTo((E) e) >= 0) break; // 如果插入元素大于等于父节点，停止调整 queue[k] = e; // 父节点下移 k = parent; } queue[k] = key; // 插入元素放到正确位置 } ~~~ * **堆调整**：将新插入的元素与父节点进行比较，如果比父节点小，则交换位置，直到满足堆的性质。 #### 3\. 获取和移除元素 `poll` 方法用于获取并移除队列头部元素： ~~~ java复制代码public E poll() { if (size == 0) return null; int s = --size; modCount++; E result = (E) queue[0]; // 获取堆顶元素 E x = (E) queue[s]; queue[s] = null; // 将最后一个元素移到堆顶位置 if (s != 0) siftDown(0, x); // 进行堆调整 return result; // 返回堆顶元素 } ~~~ * **获取堆顶元素**：返回并移除堆顶元素（数组第一个元素）。 * **堆调整**：将最后一个元素移到堆顶，然后通过 `siftDown` 方法进行堆调整。 `siftDown` 方法： ~~~ java复制代码private void siftDown(int k, E x) { if (comparator != null) siftDownUsingComparator(k, x); else siftDownComparable(k, x); } private void siftDownComparable(int k, E x) { Comparable<? super E> key = (Comparable<? super E>) x; int half = size >>> 1; while (k < half) { int child = (k << 1) + 1; // 计算左子节点索引 Object c = queue[child]; int right = child + 1; if (right < size && ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0) c = queue[child = right]; // 如果右子节点更小，使用右子节点 if (key.compareTo((E) c) <= 0) break; // 如果插入元素小于等于子节点，停止调整 queue[k] = c; // 子节点上移 k = child; } queue[k] = key; // 插入元素放到正确位置 } ~~~ * **堆调整**：将堆顶元素向下比较和交换，直到满足堆的性质。 ### 总结 `PriorityQueue` 是一个基于堆数据结构实现的无界优先级队列，提供高效的插入和删除操作。其核心在于使用堆（最小堆或最大堆）来保持元素的顺序，并通过 `siftUp` 和 `siftDown` 方法进行堆调整。 * **优点**： * 插入和删除操作的时间复杂度为 O(log n)。 * 支持按优先级排序的元素访问。 * **缺点**： * 线程不安全，需要在多线程环境中手动同步。 * 由于使用数组存储元素，扩容可能会引起性能问题。 * **使用场景**： * 任务调度：根据任务的优先级进行调度。 * 数据流处理：需要按优先级处理数据的场景。