2025年8、优先级队列

大家好，我是讯享网，很高兴认识大家。

一、什么是优先级队列

优先级队列（Priority Queue）是一种特殊的抽象数据类型（ADT），它类似于常规队列，但每个元素都有一个相关的优先级。在优先级队列中，具有较高优先级的元素会比优先级较低的元素更快地得到服务。这意味着当你从优先级队列中删除或提取元素时（通常称为出队操作），不是按照先进先出（FIFO）的原则，而是按照元素的优先级来决定下一个被处理的元素。

二、优先级队列应用的场景

任务调度： 在操作系统中，可以用于进程或线程调度，按照不同任务的重要程度或者截止时间设置优先级，优先级高的任务会被优先执行。
事件处理系统： 当系统需要处理多个具有不同优先级级别的事件时，优先级队列可以确保优先级更高的事件先被响应和处理。
中断处理： 在计算机系统中，硬件中断通常带有优先级，操作系统通过优先级队列来确定中断服务程序的执行顺序。
网络数据包处理： 路由器、交换机等网络设备中，根据协议要求或者服务质量（QoS）策略对网络包进行优先级排序，高优先级的数据包会更快地得到转发。
实时系统： 在实时控制系统中，紧急或关键的命令请求必须及时得到响应，可以利用优先级队列保证高优先级的任务先被执行。

三、实现方式

3.1、有序数组（工作中，不推荐使用该方法。）：

通过维护一个有序数组（如升序或降序），插入新元素时需要调整数组以保持排序，然后可以快速定位并删除优先级最高的元素。这种方式适用于元素数量较小且插入和删除操作不是非常频繁的情况，因为插入和删除可能涉及大量的数组元素移动。

3.2、堆（Heap）：

最大堆（Max Heap）：根节点的值大于或等于其子节点，用于实现“最大优先级队列”，每次删除操作（出队）取出的是当前堆中最大的元素。
最小堆（Min Heap）：根节点的值小于或等于其子节点，用于实现“最小优先级队列”，每次删除操作取出的是当前堆中最小的元素。

3.3、平衡二叉搜索树（Balanced Binary Search Tree, BBST）：

如AVL树、红黑树等，这些树在插入和删除后能自动保持平衡，查找、插入和删除的时间复杂度都接近O(log n)，因此也可以高效地实现优先级队列。

3.4、链表+附加数据结构：

可以使用带有额外优先级字段的链表，并结合其他数据结构（比如索引或其他形式的映射）来快速定位具有最高优先级的元素。例如，每个链表节点包含优先级信息，并且所有节点按照优先级顺序排列，或者通过一个辅助的数据结构来记录各优先级对应的链表头部。

3.5、跳表(Skip List)：

跳表是一种随机化的数据结构，它提供了近似于平衡二叉搜索树的查询效率，同时实现起来相对简单。跳表也能用来构建优先级队列。

每种实现方式都有各自的优缺点，适用场景也不同，通常根据实际需求（如内存占用、插入/删除性能、空间效率等）选择合适的实现方案。在实际应用中，基于堆的实现由于其简洁高效的性质被广泛采用。

四、代码案例

4.1、公共代码

a、队列公共接口

/ * 队列接口 * * @param <E> 队列数据类型。 */ public interface Queue<E> { 
    / * 向队列尾插入值 * * @param value 添加的值 * @return 插入成功返回 true, 插入失败返回 false */ boolean enqueue(E value); / * 从队列头获取值, 并从队列中移除获取的值 * * @return 如果队列非空返回队列头值, 否则返回 null */ E dequeue(); / * 从队列头获取值,不移除获取的值 * * @return 如果队列非空返回对头值, 否则返回 null */ E peek(); / * 检查队列是否为空 * * @return 空返回 true, 否则返回 false */ boolean isEmpty(); / * 检查队列是否已满 * * @return 满返回 true, 否则返回 false */ boolean isFull(); / * 遍历打印队列中的值。 */ void circulate(); }

讯享网

b、定义数据类型接口

讯享网/ * 定义数据类型接口 */ public interface Priority<E> { 
    / * 获取值的排序编号 * @return */ int priority(); / * 获取值 * @return */ E getValue(); }

c、创建数据类型类

package queue; / * 创建数据类型类 * * @param <E> */ public class Entry<E> implements Priority<E> { 
    //值 private E value; //排序号 private int priority; public Entry(E value, int priority) { 
    this.value = value; this.priority = priority; } / * 获取值的排序编号 * * @return */ @Override public int priority() { 
    return priority; } / * 获取值 * * @return */ @Override public E getValue() { 
    return value; } }

4.2、有序数组

a、有序数组实现类

讯享网package queue; / * 有序数组实现 * * @param <E> */ public class PriorityQueue<E extends Priority> implements Queue<E> { 
    //队列数组 private Priority[] array; //队列中值的个数 private int size; / * @param length 定义队列长度 */ public PriorityQueue(int length) { 
    array = new Priority[length]; } / * 向队列插入值 * * @param value 添加的值 * @return 插入成功返回 true, 插入失败返回 false */ @Override public boolean enqueue(E value) { 
    if (isFull()) { 
    return false; } insert(value);//调用添加方法 size++; return true; } / * 添加方法 * * @param value */ private void insert(E value) { 
    int i = size - 1; //将添加的值排序位置和队列中的值一一比较。队列值大于添加值就将值依次往后排。 while (i >= 0 && array[i].priority() > value.priority()) { 
    array[i + 1] = array[i]; i--; } array[i + 1] = value; } / * 从队列获取值, 并从队列中移除获取的值 * * @return 如果队列非空返回队列头值, 否则返回 null */ @Override public E dequeue() { 
    if (isEmpty()) { 
    return null; } E e = (E) array[size - 1];//从数组的最后一个取值 array[size - 1] = null;//将取出的值置空 size--; //队列值减1 return e; } / * 从队列头获取值,不移除获取的值 * * @return 如果队列非空返回对头值, 否则返回 null */ @Override public E peek() { 
    if (isEmpty()) { 
    return null; } E e = (E) array[size - 1]; return e; } / * 检查队列是否为空 * * @return 空返回 true, 否则返回 false */ @Override public boolean isEmpty() { 
    return size == 0; } / * 检查队列是否已满 * * @return 满返回 true, 否则返回 false */ @Override public boolean isFull() { 
    return size == array.length; } / * 遍历打印队列中的值。 */ @Override public void circulate() { 
    while (size > 0) { 
    System.out.println(array[size - 1].getValue()); size--; } } }

b、测试结果（priority 排序号越大，优先级越高，越先出队）

在这里插入图片描述
讯享网

4.2、堆

1、什么是堆

堆是一种特殊的树形数据结构，通常实现为完全二叉树或满二叉树。堆又分为两种类型最大堆（Max Heap） 和 最小堆（Min Heap）

2、什么是二叉树

二叉树是一种数据结构，它是由n（n≥0）个节点的有限集合构成，每个节点最多有两个子节点，通常分别称为左子节点和右子节点。

n：表示二叉树中的节点总数，它可以是一个任意非负整数。
n≥0：这意味着二叉树可以包含任意数量的节点，包括零个。即：
当n=0时，表示这是一棵空二叉树，它不包含任何节点。
当n>0时，表示二叉树至少包含一个节点，并且根据定义，这个节点可能还有0个、1个或2个子节点，依此类推，形成一个节点的有限集合。
二叉树如下图：每个节点最多有两个子节点，通常分别称为左子节点和右子节点。

3、什么是完全二叉树

除了最后一层外，其他层都是完全填满的，最后一层的节点都尽可能地靠左排列，允许右侧存在空节点，但左侧不允许出现空位（除非右边的所有位置也都为空）。

在这里插入图片描述

4、什么是满二叉树

所有层都被完全填满，且所有叶子节点都在最底层，没有空缺的位置。
在这里插入图片描述

5、什么是最大堆（或大顶堆）

对于任意节点i，其父节点的值大于等于（≥）它的两个子节点的值。换句话说，堆顶元素（根节点）始终是整个堆中最大的元素。
在这里插入图片描述

6、什么是最小堆（或小顶堆）

对于任意节点i，其父节点的值小于等于（≤）它的两个子节点的值。因此，在最小堆中，堆顶元素始终是最小的。
在这里插入图片描述

7、堆这种数据结构可以用数组来存储，如下图

在这里插入图片描述

特征

1、如果从索引 0 开始存储节点数据，如上图；

如何计算出任意节点 i 的父节点在哪个索引位置？
计算公式是如下（前提 i 的索引必须大于0）：

父节点索引 =（ i的索引位置 - 1）/ 2

案例：如图3的索引是4，（4-1）/2 =1，1就是3的父节点索引位置。

如何计算出任意节点 i 的子节点在哪个索引位置？
计算公式是：

讯享网案例：如图19的索引是1，他的左节点位置是3=（2*1）+1 ，他的右节点位置是4=（2*1）+2。

8、使用堆实现优先队列思路。

1、数据结构选择：

优先队列需要保证每次删除的元素都是当前队列中的最大值（对于最大堆）或最小值（对于最小堆）。因此，我们可以选择使用最大堆来实现一个“最大优先队列”（即默认出队列的是当前最大的元素），或者使用最小堆来实现“最小优先队列”（即默认出队列的是当前最小的元素）。

2、堆的初始化：

创建一个空堆，可以是一个数组来存储堆的元素。

3、插入操作：

添加新元素：
- 当需要向优先队列中插入一个新元素时，首先将该元素添加到堆数组的末尾。这样，堆的大小会增加1。
自底向上调整（Heapify Up 或者 Bubble Up）：
- 从刚插入元素的位置开始，与它的父节点进行比较。
- 如果新插入的元素比其父节点具有更高的优先级（对于最大堆来说是更大；对于最小堆来说是更小），则交换这两个元素的位置。
- 继续这个过程，不断与其新的父节点比较并可能交换位置，直到到达根节点或者已经满足堆的性质为止（即新插入的元素在正确的位置上，使得其本身及其所有祖先都大于/小于它们的孩子）。

4、删除操作（dequeue） - 删除并返回最大（或最小）值

获取堆顶元素：
- 在最大堆中，堆顶元素就是最大的元素，因此删除操作首先要返回的就是根节点的值。
替换堆顶元素：
- 将堆数组中的最后一个元素移动到根节点的位置。这样做是因为堆顶元素通常是已知的最大（或最小）值，将其移除后，用数组的最后一个元素临时填补空位，然后将数组的最后一个值赋值为null，准备进行下一轮调整。
自顶向下调整（Heapify Down 或者 Bubble Down）：
- 从新的堆顶元素开始，与它的两个子节点进行比较（如果有两个子节点的话）。
- 如果新堆顶元素不是其子节点中的最大（对于最大堆）或最小（对于最小堆）值，则与较大（或较小）的那个子节点交换位置。
- 然后，在新的位置上重复上述过程，与当前节点的子节点进行比较和可能的交换，直到整个堆重新恢复为最大堆或最小堆结构，即每个节点都满足堆的性质。

9、代码示例(这里只示例最大堆)

package queue; / * 使用最大堆实现优先队列（排序值越大，优先级越高） * * @param <E> */ public class HeapPriorityQueue<E extends Priority<E>> implements Queue<E> { 
    //创建一个空堆，可以是一个数组来存储堆的元素。 private Priority[] array; //队列值的个数。 private int size; / * @param length 设置队列长度 */ public HeapPriorityQueue(int length) { 
    array = new Priority[length]; size = 0; } / * 向队列插入值 * * @param value 添加的值 * @return 插入成功返回 true, 插入失败返回 false */ @Override public boolean enqueue(E value) { 
    if (isFull()) { 
    return false; } //添加新元素的索引位置。 int index = size; //找到新元素的父元素索引位置 int parent = (index - 1) / 2; //新元素的位置必须大于0（等于0表示数组中还没有元素），并且新元素的优先级必须大于父元素的优先级。 while (index > 0 && value.priority() > array[parent].priority()) { 
    array[index] = array[parent]; //那么将父元素替换到新元素的位置。 index = parent; //将新元素位置更改为父元素位置。 parent = (index - 1) / 2; //最后再重新计算父元素的索引位置。这样反复，直到父元素优先级大于新元素优先级才停止。 } array[index] = value;//赋值新元素的位置。 size++; return true; } / * 从队列头获取值, 并从队列中移除获取的值 * * @return 如果队列非空返回队列头值, 否则返回 null */ @Override public E dequeue() { 
    if (isEmpty()) { 
    return null; } //将第一个元素和最后一个元素的索引位置进行交换，这样最后一个值就是优先级最大的一个值 interchange(0, size - 1); E e = (E) array[size - 1];//将最后一个值取出并返回。 array[size - 1] = null;//将取出的值赋值为null,手动垃圾回收。 //将第一个被替换的值进行下潜。更新到符合的索引位置 down(0); size--; return e; } / * 位置交换方法 */ private void interchange(int i, int j) { 
    Priority t = array[i]; array[i] = array[j]; array[j] = t; } / * 元素下潜方法 * index:下潜元素的索引位置 */ private void down(int index) { 
    //获取【index索引元素】的左元素索引位置 int left = (2 * index) + 1; //获取【index索引元素】的右元素索引位置 int right = left + 1; / * 获取下潜元素中子元素优先级最高的那个元素索引，然后将下潜元素的索引位置跟该子元素索引进行替换 */ //声明一个的最高优先级索引位置变量max，假设先将下潜元素索引index表示为最高优先级索引； int max = index; //如果左元素的优先级大于下潜元素的优先级,那么左元素的优先级就是最高的。（并且left所以必须小于size-1,超过表示left索引没有值） if (left < size - 1 && array[left].priority() > array[max].priority()) { 
    max = left; } //如果右元素的优先级大于下潜元素的优先级,那么左元素的优先级就是最高的。（并且right所以必须小于size-1,超过表示right索引没有值） if (right < size - 1 && array[right].priority() > array[max].priority()) { 
    max = right; } //如果不相等，表示存在子元素的优先级大于下潜元素的优先级，那么要进行索引位置转换。 if (max != index) { 
    interchange(max, index);//将优先级最高子索引位置跟下潜元素索引位置进行替换。 down(max);//替换之后。max就是原来的index下潜元素索引。然后继续递归下潜。 } } / * 从队列头获取值,不移除获取的值 * * @return 如果队列非空返回对头值, 否则返回 null */ @Override public E peek() { 
    E e = (E) array[0]; return e; } / * 检查队列是否为空 * * @return 空返回 true, 否则返回 false */ @Override public boolean isEmpty() { 
    return size == 0; } / * 检查队列是否已满 * * @return 满返回 true, 否则返回 false */ @Override public boolean isFull() { 
    return size == array.length; } / * 遍历打印队列中的值。 */ @Override public void circulate() { 
    } }

测试结果
在这里插入图片描述