---

一、基本介绍

优先队列（Priority Queue）是一种特殊的 队列，它的元素有 优先级 属性，按照优先级出队，元素的 优先级越高，越先出队。

二、基本操作

• 插入（offer）：向优先队列中添加一个 具有优先级属性 的元素。
• 删除（poll）：从优先队列中移除 优先级最高 的元素。
• 查看（peek）：查看 优先级最高 的元素。
• 检查队列是否为空（isEmpty）。
• 检查队列是否已满（isFull）。

三、实现

1 实现的思路

优先队列的实现比较多样，例如有：

• 无序数组实现：
  • 插入：将元素插入到原先最后一个元素的下一个位置，时间复杂度为 $O(1)$。
  • 删除和查看：寻找优先级最高的元素，时间复杂度为 $O(n)$，$n$ 为队列中元素的个数。
• 有序数组实现：
  • 插入：将元素插入到合适优先级的位置，时间复杂度为 $O(n)$。
  • 删除和查看：直接找优先级最高的元素，时间复杂度为 $O(1)$。
• 大顶堆实现：
  • 插入：通过二叉堆的特性，将元素 上浮 到合适优先级的位置，时间复杂度为 $O(\log n)$。
  • 删除：将二叉堆顶部的元素 下潜 到底部，将其移出，时间复杂度为 $O(\log n)$。
  • 查看：直接查看二叉堆顶部的元素即可，时间复杂度为 $O(1)$。

注意：本文只讲解 大顶堆实现，其他实现比较简单，但时间复杂度比较高。

2 大顶堆实现

2.1 概念

要讲解大顶堆实现，需要先了解几个概念：

• 大顶堆：是一种 二叉堆，性质为：父节点的值 大于 子节点的值。
• 二叉堆：使用 完全二叉树 的树形结构实现的堆。
• 完全二叉树：是特殊的 二叉树，性质为：只有最后一层的节点没有满，且最后一层的节点只会出现在最后一层的左侧。

2.2 完全二叉树的实现方式

对于完全二叉树，有两种实现方式：

• 标准实现，即基于类型引用 TreeNode parent, left, right; 来实现。
• 基于数组的实现，其父节点和子节点的对应关系如下：
  • 以下两个假设是建立在 根节点放在数组中索引为 $0$ 的位置 这个基本条件之上的。
  • 假设父节点的索引为 $p$，则其左子节点的索引为 $2p+1$，右子节点的索引为 $2p+2$。
  • 假设子节点的索引为 $c$，则其父节点的索引为 $c/2$。注意：根节点没有父节点。

如果完全二叉树的节点个数是一定的，则推荐使用基于数组的实现，否则就老实使用标准实现。

2.3 优先队列的图示

以下是大顶堆实现的优先队列的图示：

说明：由于节点之间并未通过引用直接相连，而是通过逻辑运算将其“连接”起来，所以箭头是虚线。

2.4 对于基本操作实现的讲解

2.4.1 检查队列是否为空 ( isEmpty )

在优先队列中存储一个值 size，表示 优先队列的元素个数，如果 size == 0，则说明队列为空。

2.4.2 检查队列是否已满 ( isFull )

在本实现中，优先队列底层是一个 固定长度的 数组 data，用来存储元素，如果 size == data.length，则说明队列已满。

如果想要一个能够 自动扩容 的优先队列，使用 ArrayList 来代替数组即可。此时就不需要检查队列是否已满了。

2.4.3 查看 ( peek )

根节点的优先级最大，直接返回根节点 data[0] 即可。

2.4.4 插入 ( offer )

如果队列已满，则无需插入。否则执行插入操作：

• 先 假设 待插入元素 被放到最后一个元素的下一个位置。
• 然后将 待插入元素 与上浮到合适的位置，即依次与 比 待插入元素的优先级 小的元素 作“交换”，类似 插入排序。
• 最后将 待插入元素 放到合适的位置，并增加 size。

以下是插入 200 的示例：

• 先将其放到 79 的下一个位置。
  
• 由于 200 的优先级大于 100，所以进行交换。
  
• 由于 200 的优先级大于 133，所以进行交换。
  

2.4.5 删除 ( poll )

如果队列为空，则无需删除。否则执行删除操作：

• 先保存 堆顶元素，用于将其返回。
• 然后交换 堆顶元素 和 最后的元素，并缩小 size，让最后的索引指向 null（便于 GC 回收内存）。
• 接着将 被置换到堆顶的元素 下潜到合适的位置，即依次与 比 被置换元素的优先级 大的元素 作交换。注意：此处的交换不只针对两个元素，而是三个元素，在代码中能看到这点。
• 最后返回保存的 堆顶元素。

以下是删除优先级最大的元素的示例：

• 交换 133 和 79。
  
• 让索引 5 指向 null。
  
• 在 122, 111, 79 三个数中，由于 122 最大，所以将 79 与其交换。
  

2.5 Priority 接口

/*** 优先级接口* 一个类实现该接口后，可以获取该类的对象的优先级*/
public interface Priority {int priority(); // 获取该对象的优先级
}

2.6 Entry 类

/*** 实现了 Priority 接口的类，是能放入 优先队列 的元素，用于测试优先队列*/
public class Entry implements Priority {private String value; // 具体存储的值private int priority; // 优先级public Entry(String value, int priority) {this.value = value;this.priority = priority;}@Overridepublic int priority() {return priority;}@Overridepublic String toString() {return value + ":" + priority;}
}

2.7 PriorityQueue 类

/*** 基于大顶堆实现的优先队列** @param <E> 放入队列的元素类型，必须实现 Priority 接口*/
public class PriorityQueue<E extends Priority> {/*** 向队尾插入值，并将其放到合适的位置** @param value 待插入值* @return 若队列已满，则返回 false；否则返回 true，表示插入成功*/public boolean offer(E value) {if (isFull()) {return false;}int child = up(value); // 将插入值 上浮 到合适位置data[child] = value; // 在合适位置赋值size++; // 元素数量加一return true;}/*** 获取优先级最大的元素，并将其取出** @return 如果队列非空，则返回队首的值；否则返回 null*/public E poll() {if (isEmpty()) {return null;}E value = (E) data[0]; // 保存优先级最大的元素，之后将其返回data[0] = data[--size]; // 交换 优先队列中 最后一个元素 与 优先级最大的元素data[size] = null; // help GCdown(0); // 将被交换到索引为 0 的最后一个元素 下潜 到合适位置return value;}/*** 获取优先级最大的元素，但不将其取出** @return 如果队列非空，则返回队首的值；否则返回 null*/public E peek() {if (isEmpty()) {return null;}return (E) data[0];}/*** 检查优先队列是否为空** @return 如果优先队列为空，则返回 true；否则返回 false*/public boolean isEmpty() {return (size == 0);}/*** 检查优先队列是否已满** @return 如果优先队列已满，则返回 true；否则返回 false*/public boolean isFull() {return (size == data.length);}public PriorityQueue(int capacity) {data = new Priority[capacity];}/*** 将插入的值 上浮 到合适的位置（下潜 比插入值优先级小的 元素）** @param value 插入的值* @return 合适位置的索引*/private int up(E value) {int child = size; // 获取待插入元素的索引int parent = getParent(child); // 获取其父节点的索引// 类似于 插入排序while (child > 0 // 直到 到达根节点&& value.priority() > data[parent].priority()) { // 或者 待插入元素的优先级 小于等于 其父节点的优先级data[child] = data[parent]; // 将 父节点的值 赋值给 子节点，表示下潜父节点child = parent; // 将 子节点 更新到 父节点 处parent = getParent(parent); // 将 父节点 更新到 父节点的父节点 处}return child; // 返回待插入元素元素的合适索引}/*** 将指定的索引 下潜 到合适的位置（上浮 比指定值优先级大的 元素）** @param parent 指定索引*/private void down(int parent) {int left = getLeft(parent); // 获取左子节点的索引int right = left + 1; // 获取右子节点的索引int max = parent; // max 是父节点和两个子节点中，优先级最大的元素的索引。一开始假设 父节点 的优先级最大if (left < size // 防止 left 超过已有的元素个数&& data[max].priority() < data[left].priority()) { // 寻找 左子节点 和 优先级最大元素 中优先级更大的元素索引max = left;}if (right < size // 防止 right 超过已有的元素个数&& data[max].priority() < data[right].priority()) { // 寻找 右子节点 和 优先级最大元素 中优先级更大的元素索引max = right;}if (max == parent) { // 如果父节点的优先级最大，则不需要下潜父节点return;}swap(parent, max); // 下潜 父节点 到 更大的子节点 处，然后 max 就成为被下潜节点的索引了down(max); // 递归检查这个节点，并在必要时下潜它}/*** 获取指定 子节点 对应的 父节点 的索引* @param child 子节点的索引* @return 其对应的父节点的索引*/private static int getParent(int child) {return (child - 1) >> 1;}/*** 获取指定 父节点 对应的 左子节点 的索引* @param parent 父节点的索引* @return 其对应的左子节点的索引*/private static int getLeft(int parent) {return (parent << 1) + 1;}/*** 交换 data 中的两个指定索引的元素* @param idx1 指定索引1* @param idx2 指定索引2*/private void swap(int idx1, int idx2) {Priority temp = data[idx1];data[idx1] = data[idx2];data[idx2] = temp;}private Priority[] data;    // 储存数据的数组private int size;           // 优先队列的元素个数
}

2.8 测试类

public class Test {public static void main(String[] args) {PriorityQueue<Entry> queue = new PriorityQueue<>(5); // 构建一个长度为 5 的优先队列// 先添加 5 个元素queue.offer(new Entry("task1", 4));queue.offer(new Entry("task2", 3));queue.offer(new Entry("task3", 2));queue.offer(new Entry("task4", 5));queue.offer(new Entry("task5", 1));System.out.println(queue.offer(new Entry("task6", 6))); // 优先队列已满，无法添加新元素System.out.println(queue.peek()); // 查看优先级最大的元素// 依次删除优先级最大的元素System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll()); // 优先队列为空，无法删除}
}

2.9 测试结果

false	// offer()
task4:5 // peek()
task4:5 // poll()
task1:4 // poll()
task2:3 // poll()
task3:2 // poll()
task5:1 // poll()
null	// poll()

四、应用

1. 排序问题

• 查找第 k 个最小元素：通过维护一个大小为 k 的优先队列（最小堆），可以高效地 找到数据集合中的第 k 个最小元素。
• 堆排序：堆排序算法使用优先队列（通常是二叉堆）作为底层数据结构，通过 不断删除堆顶元素（即当前最小值）并重新调整堆结构，实现数据的排序。

2. 图算法

• 最短路径算法：如 Dijkstra 算法，利用优先队列（最小堆）来不断选择 当前未处理节点中距离源点最近的节点，逐步构建最短路径树。
• 最小生成树算法：如 Prim 算法，在构建最小生成树的过程中，也使用了优先队列（最小堆）来选择 当前未加入生成树集合中权重最小的边。

3. 任务调度

• 系统任务调度：在操作系统中，任务调度器可以根据任务的优先级来 分配 CPU 时间片，优先处理优先级高的任务。
• 多线程编程：在多线程编程中，可以使用优先队列来 管理线程的执行顺序，确保优先级高的线程能够优先获得执行机会。

4. 事件驱动仿真

• 顾客排队算法：在模拟顾客排队等待服务的场景中，可以使用优先队列来 管理顾客的优先级（如根据等待时间、顾客重要性等因素），确保优先级高的顾客能够优先获得服务。

5. 数据压缩

• 赫夫曼编码：赫夫曼编码是一种广泛使用的数据压缩算法，它根据 字符出现的频率 构建优先队列（通常是最小堆），然后基于队列中的元素构建赫夫曼树，最终生成压缩编码。

6. 网络路由算法

• 路由选择：在网络路由算法中，路由器可以使用优先队列来 管理路由表中的路由信息，确保在多个可能的路由中选择优先级最高（如延迟最小、带宽最大）的路由。

7. 缓存管理

• 缓存替换策略：在缓存管理系统中，如操作系统的页面置换算法，可以使用优先队列来 管理缓存中的页面，根据页面的优先级（如访问频率、最近访问时间等）来决定哪些页面应该被替换出缓存。

五、总结

优先队列是一种特殊的队列，具有 优先级越大，越靠前 的性质，一般使用 大顶堆 来实现。此外，它可以应用到 排序、各种图（和 树）的算法 等多个领域，这些应用充分利用了优先队列能够 高效管理具有优先级元素 的能力，从而提高了系统的性能和效率。