1 PriorityQueue 简介
PriorityQueue 是 Java 中的一个基于优先级堆的优先队列实现，它能够在 O(log n) 的时间复杂度内实现元素的插入和删除操作，并且能够自动维护队列中元素的优先级顺序。与普通队列不同，PriorityQueue 不是先进先出的，而是按照元素的优先级进行排序。当你往 PriorityQueue 中插入一个元素时，它会自动根据元素的优先级将其插入到合适的位置。当你从 PriorityQueue 中删除一个元素时，它会自动将优先级最高的元素出队。
2 PriorityQueue 的使用
-
创建 PriorityQueue 对象：
PriorityQueue<String> priorityQueue = new PriorityQueue<>(); -
添加元素：
priorityQueue.offer("沉默王二"); priorityQueue.offer("陈清扬"); priorityQueue.offer("小转铃"); -
遍历并打印元素：
while (!priorityQueue.isEmpty()) {System.out.print(priorityQueue.poll() + " "); } -
指定优先级顺序：
PriorityQueue<String> priorityQueue = new PriorityQueue<>(Comparator.reverseOrder());
3 PriorityQueue 的主要作用
PriorityQueue 的主要作用是维护一组数据的排序，使得取出数据时可以按照一定的优先级顺序进行。当我们调用 poll() 方法时，它会从队列的顶部弹出最高优先级的元素。它在任务调度、事件处理等场景中广泛应用，也常用于实现 Dijkstra 算法、Prim 算法、Huffman 编码等算法。
-
Dijkstra 算法：用于计算带权图中的最短路径。该算法采用贪心策略，在遍历图的过程中，每次选取当前到源点距离最短的一个顶点，并以它为中心进行扩展，更新其他顶点的距离值。经过多次扩展，可以得到源点到其它所有顶点的最短路径。
-
Prim 算法：用于求解最小生成树。该算法从任意一个顶点开始，逐渐扩展生成树的规模，每次选择一个距离已生成树最近的顶点加入到生成树中，使得生成树的所有边的权值之和最小。
-
Huffman 编码：一种基于霍夫曼树的压缩算法，用于将一个字符串转换为二进制编码以进行压缩。该算法通过建立霍夫曼树，将出现频率较高的字符用较短的编码表示，而出现频率较低的字符用较长的编码表示，从而实现对字符串的压缩。在解压缩时，根据编码逐步解析出原字符串。
4 PriorityQueue 的底层实现
PriorityQueue 的底层是基于堆（Heap）实现的。堆是一种完全二叉树，其中每个节点的值都小于或等于其子节点的值（小顶堆），或者每个节点的值都大于或等于其子节点的值（大顶堆）。堆的特点是根节点的值最小（小顶堆）或最大（大顶堆），并且任意非根节点 i 的值都不大于（或不小于）其父节点的值。
5 堆的存储结构
堆可以使用数组来存储，而不需要使用指针等额外的空间。假设节点下标为 i，则其父节点下标为 (i - 1) / 2，其左子节点下标为 2 * i + 1，其右子节点下标为 2 * i + 2。
-
完全二叉树：
1/ \2 3/ \ /4 5 6 -
小顶堆：
1/ \2 3/ \ / \ 4 5 6 7 -
大顶堆：
8/ \7 5/ \ / \ 6 4 2 1
6 方法剖析
6.1 add() 和 offer()
add(E e) 和 offer(E e) 的语义相同，都是向优先队列中插入元素。区别在于，add() 在插入失败时会抛出异常，而 offer() 则会返回 false。对于 PriorityQueue，这两个方法的实现基本相同。
-
offer(E 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; // 队列原来为空，插入第一个元素elsesiftUp(i, e); // 调整堆结构return true; } -
siftUp(int k, E x)：
private void siftUp(int k, E x) {while (k > 0) {int parent = (k - 1) >>> 1; // 计算父节点下标Object e = queue[parent];if (comparator.compare(x, (E) e) >= 0)break;queue[k] = e;k = parent;}queue[k] = x; }
siftUp() 方法的作用是从指定位置 k 开始，将元素 x 逐层与父节点进行比较并交换，直到满足 x >= queue[parent] 为止。
6.2 element() 和 peek()
element() 和 peek() 的语义完全相同，都是获取但不删除队首元素（即优先级最高的元素）。区别在于，element() 在队列为空时会抛出异常，而 peek() 则会返回 null。
- peek()：
public E peek() {if (size == 0)return null;return (E) queue[0]; // 返回堆顶元素 }
6.3 remove() 和 poll()
remove() 和 poll() 的语义也完全相同，都是获取并删除队首元素。区别在于，remove() 在队列为空时会抛出异常，而 poll() 则会返回 null。
-
poll()：
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(int k, E x)：
private void siftDown(int k, 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 && comparator.compare((E) c, (E) queue[right]) > 0)c = queue[child = right]; // 选择较小的孩子if (comparator.compare(x, (E) c) <= 0)break;queue[k] = c;k = child;}queue[k] = x; }
siftDown() 方法的作用是从指定位置 k 开始，将元素 x 逐层向下与左右孩子中较小的那个交换，直到满足 x <= queue[child] 为止。
6.4 remove(Object o)
remove(Object o) 方法用于删除队列中与指定对象 o 相等的元素（如果有多个相等，只删除一个）。该方法不是 Queue 接口内的方法，而是 Collection 接口的方法。
- remove(Object o)：
public boolean remove(Object o) {int i = indexOf(o); // 查找元素下标if (i == -1)return false;int s = --size;if (s == i)queue[i] = null; // 删除最后一个元素else {E moved = (E) queue[s];queue[s] = null;siftDown(i, moved); // 调整堆结构}return true; }
remove(Object o) 方法分为两种情况：
- 删除的是最后一个元素，直接删除即可，不需要调整。
- 删除的不是最后一个元素，从删除点开始以最后一个元素为参照调用
siftDown()方法进行调整。
6.5 小结
PriorityQueue 提供了多种方法来插入、获取和删除元素，并自动维护堆的性质。add() 和 offer() 用于插入元素，element() 和 peek() 用于获取但不删除队首元素，remove() 和 poll() 用于获取并删除队首元素，remove(Object o) 用于删除指定元素。这些方法在操作失败时的处理方式有所不同，但核心逻辑都是通过 siftUp() 和 siftDown() 方法来维护堆的性质。
7 总结
PriorityQueue 是一个非常常用的数据结构，适用于需要按照优先级顺序处理元素的场景。它的底层实现是一个数组，通过堆的性质来维护元素的顺序。取出元素时按照优先级顺序（从小到大或者从大到小）进行取出。如果需要指定排序，元素必须实现 Comparable 接口或者传入一个 Comparator 来进行比较。
8 思维导图
9 参考链接
10 张手绘图详解Java 优先级队列PriorityQueue
