当前位置：首页 > news >正文

数据结构（优先级队列：Priority Queue）

news 文章来源：https://blog.csdn.net/eternal__day/article/details/144460121 2024/12/27 8:15:09

前言：

在计算机科学中，队列是一种非常常见的数据结构，它遵循先进先出（FIFO）的原则，也就是说，先进入队列的元素会先被处理。然而，在许多实际应用中，我们不仅仅需要按顺序处理元素，还希望能根据每个元素的“优先级”来决定处理的顺序。这时，优先级队列（Priority Queue）就显得尤为重要。

优先级队列是一种特殊的队列，它的每个元素都与一个优先级相关联。在优先级队列中，优先级高的元素会比优先级低的元素更早被取出处理。优先级队列常用于任务调度、事件驱动的模拟系统以及各种图算法等场景。在这些应用中，任务的执行顺序并不是简单的时间顺序，而是由任务的重要性或紧急性决定的。

例如，在操作系统的调度算法中，某些任务（比如响应时间要求高的任务）可能比其他任务更需要优先执行。又比如，在图算法中，我们需要选择最短路径的节点，而优先级队列恰好能提供高效的方式来维护和更新这些节点。

在这篇博客中，我们将深入探讨优先级队列的基本概念、常见实现方法、以及它在实际应用中的表现。我们还将展示如何在Java中使用标准库中的PriorityQueue类，并手动实现一个基于数组的优先级队列。通过这些内容，希望你能够理解优先级队列的核心原理，并能够在实际项目中灵活应用这一强大的数据结构。

1.优先级队列讲解：

1.1 概念

前面介绍过队列，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适，比如：在手机上玩游戏的时候，如果有来电，那么系统应该优先处理打进来的电话；初中那会班主任排座位时可能会让成绩好的同学先挑座位。在这种情况下，数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)。

1.2 队列与优先级队列的区别

队列：队列是一个线性数据结构，遵循先进先出（FIFO，First In First Out）原则，即最先插入队列的元素会最先被取出。它主要用于一些按顺序执行的场景，如打印任务、请求处理等。
优先级队列：与队列不同，优先级队列会根据元素的优先级来决定处理顺序。优先级高的元素优先被取出，而不是按插入的顺序。优先级队列通常用于需要根据优先级执行的任务调度或动态排序场景。

1.3 优先级队列的特点

优先级：每个元素都有一个关联的优先级。这个优先级通常是一个数值，较大的数值表示较高的优先级（或者在某些应用中，较小的数值表示较高的优先级，具体取决于实现）。当队列中的元素有不同的优先级时，优先级较高的元素会先被处理。
动态排序：优先级队列中的元素不是按插入顺序排列的，而是按照优先级动态排序。每次取出队列元素时，总是优先取出优先级最高的元素。
堆的实现：优先级队列通常使用堆（Heap）这种数据结构来实现。堆是一种完全二叉树（或完全树），它可以在对数时间内高效地插入和删除元素，同时保持优先级队列的特性。
非线性结构：与线性结构的队列和栈不同，优先级队列的元素存储在一个满足堆特性的树形结构中，因此它并不遵循FIFO顺序。

1.4 基本操作

优先级队列支持以下几种基本操作：

插入元素：将一个新的元素加入队列，同时根据优先级插入到正确的位置。
删除元素：通常删除队列中优先级最高（最小或最大）的元素。这个操作通常称为“取出”操作。
查看堆顶元素：查看当前优先级队列中优先级最高的元素，但不将其删除。

这些操作可以通过使用堆这种数据结构来高效地实现。具体来说：

插入：将一个元素添加到队列末尾，调整堆使其满足堆的特性（时间复杂度：O(log n)）。
删除：删除堆顶元素，并将堆的最后一个元素移到堆顶，然后调整堆（时间复杂度：O(log n)）。
查看堆顶元素：直接返回堆顶元素，不需要修改堆（时间复杂度：O(1)）。

1.5. 最小堆与最大堆

优先级队列可以根据不同的应用需求，选择不同类型的堆来维护队列的顺序。常见的堆有两种：

最小堆（Min-Heap）：堆顶元素是最小的元素，每次删除操作都会删除优先级最低的元素。常用于优先级队列中较小的值具有较高优先级的场景。
- 例如：操作系统的任务调度时，任务的优先级数字越小，表示任务越紧急。
最大堆（Max-Heap）：堆顶元素是最大的元素，每次删除操作都会删除优先级最高的元素。常用于优先级队列中较大的值具有较高优先级的场景。
- 例如：任务调度时，任务的优先级数字越大，表示任务越重要，越早处理。

1.6. 优先级队列的应用

优先级队列在许多应用场景中都有广泛的应用，尤其是在需要按优先级处理任务的情况下。以下是一些常见的应用场景：

任务调度：操作系统或任务调度系统中，优先级队列用于管理具有不同优先级的任务。优先级高的任务会被首先执行。
图算法：
- Dijkstra最短路径算法：在求解图的最短路径问题时，优先级队列用于存储和更新待处理节点的最短路径值。每次都取出当前最短的路径进行更新。
- A*搜索算法：用于路径寻找问题，结合优先级队列和启发式搜索策略来提高搜索效率。
事件驱动模拟：优先级队列可以用于事件调度，确保优先级高的事件先被处理。例如，模拟系统中的事件按时间顺序发生，可以通过优先级队列来动态管理事件的处理顺序。
合并多个已排序的序列：多个已排序的列表或流数据合并时，优先级队列可以有效地维护最小或最大元素，帮助高效地合并这些数据流。

2. 优先级队列的常见实现

2.1. 可以通过这个网站来动态展示过程：

Binary Heap (Priority Queue) - VisuAlgo

2.2.1 堆讲解

JDK1.8中的PriorityQueue底层使用了堆这种数据结构，而堆实际就是在完全二叉树的基础上进行了一些调整。

如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki 且 Ki= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

堆中某个节点的值总是不大于或不小于其父节点的值；

堆总是一棵完全二叉树。

2.2 堆的存储方式

从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储，

注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。

将元素存储到数组中后，可以根据二叉树的性质对树进行还原。假设i为节点在数组中的下标，则有：

如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2

如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子

如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子

2.3 堆的创建

2.3.1 堆向下调整

对于集合{ 27,15,19,18,28,34,65,49,25,37 }中的数据，如果将其创建成堆呢？

仔细观察上图后发现：根节点的左右子树已经完全满足堆的性质，因此只需将根节点向下调整好即可。

向下过程(以大堆为例)：

1. 让parent标记需要调整的节点，child标记parent的左孩子(注意：parent如果有孩子一定先是有左孩子)

2. 如果parent的左孩子存在，即:child < size，进行以下操作，直到parent的左孩子不存在

            parent右孩子是否存在，存在找到左右孩子中最小的孩子，让child进行标

           将parent与较小的孩子child比较，如果：

            parent小于较小的孩子child，调整结束

            否则：交换parent与较小的孩子child，交换完成之后，parent中大的元素向下移动，可能导致子树不满足对的性质，因此需要继续向下调整，即parent = child；child = parent*2+1; 然后继续2。

BigRootPile()方法通过从最后一个非叶子节点开始，依次调整每个节点，最终构建一个最大的堆。
ShiftDown()方法通过比较父节点左右子节点的值，进行交换操作，保证堆的性质被满足，分层地迭代调整堆。
swap()交换备份中的两个要素的方法。

1.BigRootPile()方法

思路：
BigRootPile()的作用是从数组的最后一个非叶子节点开始，逐步将堆的性质调整好，最终构建一个最大的堆。它通过不断调用的ShiftDown()方法来调整节点的位置。

this.UesSize-1-1)/2：
这部分代码计算的是最后一个非叶子节点的索引。对于一个堆来说，叶子节点的位置从(n / 2)开始（其中n是堆中元素的个数）。最后一个非叶子节点的位置就是n / 2 - 1。所以这里this.UesSize - 1 - 1是以获得数组的最后一个非叶子节点的下标。

for (int parent = (this.UesSize-1-1)/2; parent >=0 ; parent--)：
设想代码通过从最后一个非叶子节点开始，从右到左、从下到上逐个遍历父节点，调用ShiftDown()方法调整堆的结构。遍历到parent == 0时，整个堆会被调整成最大堆。

ShiftDown(parent, this.UesSize)：
对每个父节点执行ShiftDown()操作，这个操作会保证从该父节点开始，下沉整个子树，依次是最大堆的特性。

2.ShiftDown(int parent, int uesdsize)方法

思路：
ShiftDown目的是给定的父节点值与子节点进行比较，调整堆结构，保证父节点大于或等于其子节点。如果堆的性质被破坏，就进行调整，直到子树满足最大堆特性。

int child = parent * 2 + 1;：
这个计算式是完全根据二叉树的性质的。对于堆中的一个父节点，其左子节点的索引是2 * parent + 1，右子节点的索引是2 * parent + 2。

while (child < uesdsize)：
进入循环，检查当前节点的左子节点是否在有效范围内。循环直到没有子节点或所有子节点已经满足堆的条件。

if (child + 1 < uesdsize && arr[child] < arr[child + 1])：
代码判断当前节点的右子节点是否存在，并且如果存在，判断右子节点是否大于左子节点。如果是这样，则更新child为右子节点的索引。这个操作保证了child是当前父节点的比较大子节点，确保父节点和增加的子节点进行交换。

if (arr[parent] < arr[child])：
如果父节点的值小于子节点的值（child是左右子节点中增加的一个），就交换父节点与子节点的位置。调用swap(arr, child, parent)进行交换，调整父节点与子节点的位置。

parent = child; child = parent * 2 + 1;：
交换后，更新父节点的位置为交换后的子节点，并计算新的子节点位置。继续下去检查子树，保持堆的性质。

else { break; }：
如果当前父节点的值已经大于或等于其增量子节点的值，说明堆的性质已经满足，退出循环。

3.swap(int[] arr, int i, int j)方法

思路：
swap()方法交换阵列中两个元素的值，常用于堆调整操作中的元素交换。

arr[i]和arr[j]交换值，使用临时标志tmp来避免直接覆盖导致损失值。

2.3.2 堆的添加

堆的插入总共需要两个步骤：

1. 先将元素放入到底层空间中(注意：空间不够时需要扩容)

2. 将最后新插入的节点向上调整，直到满足堆的性质

1. push(int val) 方法

思路：

该方法实现了优先级队列的插入操作，目的是将一个新元素 val 插入到堆中，并保持堆的性质。

判断堆是否满：

使用 isEmpty() 方法判断堆是否已经满了。如果堆已经满了，就需要扩展数组的大小来容纳更多元素。堆的实际元素数由 UesSize 表示，arr.length 是堆的容量。
扩展数组：如果堆满了，就通过 Arrays.copyOf(arr, arr.length * 2) 将堆数组的容量扩大一倍，以便插入更多元素。

将新元素插入堆：

将新元素 val 插入到堆的末尾，即将其存入 arr[UesSize]。
堆大小更新：之后，堆的大小 UesSize 会增加，表示堆中元素的个数。

执行“上浮”操作：

在堆中插入元素后，需要执行 siftup() 操作来保持堆的结构。上浮操作会将新插入的元素与其父节点比较，并在必要时进行交换，直到堆的性质（比如最大堆或最小堆）得到维护。

更新堆大小：

最后，UesSize++ 将堆的大小增加 1，表示堆中已经插入了一个新的元素。

2.isEmpty() 方法

判断堆是否已满：isEmpty() 用来判断堆是否已经满了。UesSize 表示当前堆中已存储的元素个数，而 arr.length 表示数组的容量。当 UesSize 等于 arr.length 时，说明堆已满，需要扩展数组来容纳更多元素。

3. siftup(int child) 方法

思路：

siftup() 是堆中常用的操作，用于维护堆的结构。当一个新元素被插入堆的末尾时，它可能违反了堆的性质（例如，在最大堆中，如果新元素大于父节点，则父节点应该交换位置）。通过上浮操作来恢复堆的性质。

计算父节点索引：
对于堆中的任何一个节点（包括新插入的节点），其父节点的索引是 (child - 1) / 2。这段代码首先计算出插入元素 child 的父节点 parent 的索引。

上浮过程：
通过 while (parent >= 0) 循环检查父节点是否存在。循环的条件是 parent >= 0，确保我们没有越过堆的顶部。

判断是否需要交换：
如果当前节点 arr[child] 的值大于父节点 arr[parent] 的值，则需要交换这两个元素的位置，因为堆的性质要求父节点的值要大于等于子节点的值（在最大堆中）。如果满足这个条件，就交换 arr[child] 和 arr[parent] 的位置，并更新 child 为父节点的索引，继续向上检查。

更新父节点索引：
交换之后，更新 child 为交换后的父节点，并重新计算新的父节点索引 parent = (child - 1) / 2。然后继续判断新的父节点与子节点之间的关系。

停止条件：
如果当前节点已经比父节点大，或者已经到达堆顶，parent 会变为负数，循环会停止。

2.3.3 弹出堆顶元素

注意：堆的删除一定删除的是堆顶元素。具体如下：

1. 将堆顶元素对堆中最后一个元素交换

2. 将堆中有效数据个数减少一个

3. 对堆顶元素进行向下调整

逐步分析：

保存根元素的值：

int val = arr[0];

首先，获取堆中的根元素（即数组 arr[0]），并将其保存到 val 变量中。这个值将是我们需要返回的元素，因为在优先级队列中，poll() 的作用就是返回并移除堆中的根元素。

交换根元素与堆的最后一个元素：

swap(arr, 0, UesSize - 1);

为了删除根元素（即 arr[0]），我们将根元素与堆的最后一个元素 arr[UesSize - 1] 交换。这是一个常见的堆操作，目的是将堆的最后一个元素放到根位置，为后续的堆调整（“下沉”操作）做准备。
交换后的堆元素数量 UesSize 会减少，因此堆的最后一个元素的位置不再有效，但它的值已经被放到根的位置。

下沉操作（ShiftDown）：

ShiftDown(0, UesSize - 1);

在将根元素与最后一个元素交换后，新的根元素（原最后一个元素）可能不满足堆的性质（例如，在最大堆中，它可能比某些子节点小）。
ShiftDown() 方法是堆的一个调整操作，用来“下沉”新的根元素，确保堆的性质得以恢复。ShiftDown() 会将当前节点与其较大的子节点交换位置，直到堆的结构重新符合最大堆或最小堆的要求。
ShiftDown 的工作原理：

从根节点开始，比较当前节点与左右子节点的值。
如果子节点的值更大（在最大堆中），则交换当前节点和最大的子节点。
交换后，递归执行下沉操作，直到堆满足堆的性质，或者当前节点的值大于等于子节点的值。

更新堆大小：

UesSize--;

删除根元素后，堆的元素数量减少 1。通过 UesSize-- 更新堆的大小。

返回删除的根元素：

return val;

最后，返回最初保存的根元素 val，即 poll() 操作的结果。

2.3.4 堆排的实现

交换堆顶元素与堆的最后一个元素，将最大（或最小）元素放到数组的正确位置；
通过 ShiftDown 恢复堆的结构，确保剩余部分仍然满足堆的性质；
逐步缩小待排序的范围，直到所有元素排好序。

逐步分析：

1. 初始化 end

int end = UesSize - 1;

这里 end 被设置为堆中最后一个元素的索引。UesSize 表示堆的当前大小，所以 UesSize - 1 就是堆数组的最后一个元素的索引。
end 变量表示当前待排序的范围，从堆的末尾开始逐步减小。

2. 循环逐步排序

while (end > 0) {

进入一个 while 循环，直到 end 等于 0。每次循环都会将堆顶元素（当前最大元素）交换到堆的末尾，并减少待排序范围（即减小 end）。

3. 交换堆顶和当前元素

swap(arr, 0, end);

将堆顶元素（arr[0]）与当前的 end 元素交换位置。因为堆的根元素是当前堆中最大的元素（在最大堆中），所以将堆顶元素交换到堆的末尾。这样，堆的最大元素被放置在正确的位置。

4. 调整堆结构（下沉操作）

ShiftDown(0, end);

交换根元素和末尾元素后，新的根元素可能不符合堆的性质，因此需要执行 ShiftDown() 来恢复堆的性质（最大堆或最小堆）。
ShiftDown(0, end) 从堆的根开始，进行下沉操作。它会确保交换后的根元素被调整到正确的位置，使得新的堆顶元素符合堆的性质。

5. 减小待排序范围

end--;

end-- 表示将堆的待排序范围缩小1，因为已经将当前最大元素（堆顶元素）放到最终位置，并且不再参与后续的排序操作。

6. 完成排序

当 end 达到 0 时，所有元素都已经排好序。堆排序的时间复杂度是 O(n log n)，这段代码的循环会执行 n-1 次，每次通过 swap 和 ShiftDown 调整堆结构。

2.3.4.1堆排序的过程概述

建立最大堆：首先，heapSort() 方法假设传入的数组已经是一个堆。堆的构建需要通过一系列的上浮或下沉操作来确保堆的性质。我们通过 ShiftDown 操作来调整堆。
排序过程：
- 每次将堆顶（当前最大元素）与数组的最后一个元素交换。
- 然后，通过 ShiftDown 操作调整堆，使剩余部分保持堆的结构。
- 每次交换后，堆的大小减少1，end 变量逐渐减小，直到所有元素排好序。
结束条件：当 end == 0 时，排序完成，整个数组已按升序排列。

2.3.4.2 堆排序的时间复杂度

时间复杂度：
- 建堆的时间复杂度是 O(n)，因为需要对所有非叶子节点执行 ShiftDown 操作。
- 对于排序过程中的每次交换和堆调整，ShiftDown 操作的时间复杂度为 O(log n)，因为堆的高度为 log n。
- 在 heapSort() 中，循环执行了 n-1 次，每次操作的时间复杂度是 O(log n)。因此，排序的总时间复杂度是 O(n log n)。
空间复杂度：
- 堆排序是一种原地排序算法，不需要额外的辅助空间。它直接在原数组上进行排序，因此空间复杂度是 O(1)。

2.4 建堆的时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

2.5 代码展示

package Tree;import java.util.Arrays;public class text {public int[] arr;public int UesSize ;public text() {this.arr = new int[10];}public void inintElmp(int[] array){for (int i = 0; i < array.length; i++) {this.arr[i] = array[i];this.UesSize++;}}public void BigRootPile(){for (int parent = (this.UesSize-1-1)/2; parent >=0 ; parent--) {ShiftDown(parent,this.UesSize);}}private void ShiftDown(int parent,int uesdsize) {int child = parent * 2 + 1;while (child < uesdsize) {if (child + 1 < uesdsize && arr[child] < arr[child + 1]) {child++;}if(arr[parent] < arr[child]){swap(arr,child,parent);parent = child;child = parent * 2 + 1;}else {break;}}}private void swap(int[] arr,int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}public void push(int val){if(isEmpty()){arr =  Arrays.copyOf(arr,arr.length*2);}arr[UesSize] = val;siftup(UesSize);UesSize++;}public boolean isEmpty() {return UesSize == arr.length;}private void siftup(int child) {int parent = (child-1)/2;while (parent>=0) {if(arr[parent] < arr[child]){swap(arr,child,parent);child = parent;parent = (child-1)/2;}}}public int poll() {int val = arr[0];swap(arr,0,UesSize-1);ShiftDown(0, UesSize-1);UesSize--;return val;}public void heapSort() {int end = UesSize-1;while (end > 0) {swap(arr,0,end);ShiftDown(0, end);end--;}}
}

结语

优先级队列作为一种重要的数据结构，在许多实际应用中都扮演着至关重要的角色。无论是在操作系统的任务调度、图算法中的最短路径计算，还是事件驱动模拟中，优先级队列都能高效地管理和调度具有不同优先级的任务和事件。

通过本文的介绍，我们详细探讨了优先级队列的基本概念、实现方式以及实际应用。我们理解了优先级队列与普通队列的区别，学习了堆这种数据结构在优先级队列中的应用，并展示了如何通过 Java 中的 PriorityQueue 类来实现这一数据结构。此外，我们还手动实现了基于数组的优先级队列，深入了解了堆的构建、插入、删除等操作的细节，掌握了如何利用堆的性质高效地完成优先级队列的功能。

优先级队列的实现方式多种多样，堆是最常用且高效的方式，适用于大多数需求。而在一些特定应用中，可能还会采用其他的数据结构来优化性能或者适应特定场景的需求。通过本篇博客的学习，您不仅能够理解优先级队列的工作原理，还能够在实际开发中灵活应用这一数据结构来解决复杂的任务调度、图遍历和排序问题。

未来，随着技术的不断发展，优先级队列在新的应用场景中的作用将愈发重要。例如，在人工智能、机器学习、实时系统等领域，优先级队列的高效性和灵活性将为我们提供更多的解决方案。

希望这篇文章能帮助你更好地理解优先级队列，并能够将其应用到实际项目中。如果你对优先级队列或其他数据结构有任何疑问，欢迎随时交流探讨！

前言：