当当网电子商务网站建设,上海网站seo优化,怎么才能免费建网站,如何查询一个网站所属的主机前言#xff1a;
在计算机科学中#xff0c;队列是一种非常常见的数据结构#xff0c;它遵循先进先出#xff08;FIFO#xff09;的原则#xff0c;也就是说#xff0c;先进入队列的元素会先被处理。然而#xff0c;在许多实际应用中#xff0c;我们不仅仅需要按顺序…前言
在计算机科学中队列是一种非常常见的数据结构它遵循先进先出FIFO的原则也就是说先进入队列的元素会先被处理。然而在许多实际应用中我们不仅仅需要按顺序处理元素还希望能根据每个元素的“优先级”来决定处理的顺序。这时优先级队列Priority Queue就显得尤为重要。
优先级队列是一种特殊的队列它的每个元素都与一个优先级相关联。在优先级队列中优先级高的元素会比优先级低的元素更早被取出处理。优先级队列常用于任务调度、事件驱动的模拟系统以及各种图算法等场景。在这些应用中任务的执行顺序并不是简单的时间顺序而是由任务的重要性或紧急性决定的。
例如在操作系统的调度算法中某些任务比如响应时间要求高的任务可能比其他任务更需要优先执行。又比如在图算法中我们需要选择最短路径的节点而优先级队列恰好能提供高效的方式来维护和更新这些节点。
在这篇博客中我们将深入探讨优先级队列的基本概念、常见实现方法、以及它在实际应用中的表现。我们还将展示如何在Java中使用标准库中的PriorityQueue类并手动实现一个基于数组的优先级队列。通过这些内容希望你能够理解优先级队列的核心原理并能够在实际项目中灵活应用这一强大的数据结构。 1.优先级队列讲解
1.1 概念
前面介绍过队列队列是一种先进先出(FIFO)的数据结构但有些情况下操作的数据可能带有优先级一般出队 列时可能需要优先级高的元素先出队列该中场景下使用队列显然不合适比如在手机上玩游戏的时候如 果有来电那么系统应该优先处理打进来的电话初中那会班主任排座位时可能会让成绩好的同学先挑座位。 在这种情况下数据结构应该提供两个最基本的操作一个是返回最高优先级对象一个是添加新的对象。这种数 据结构就是优先级队列(Priority Queue)。
1.2 队列与优先级队列的区别 队列队列是一个线性数据结构遵循先进先出FIFOFirst 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 {k0k1 k2…kn-1}把它的所有元素按完全二叉树的顺序存储方式存储 在一 个一维数组中并满足Ki 且 Ki K2i1 且 Ki K2i2) i 012…则称为 小堆(或大 堆)。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆。
堆的性质 堆中某个节点的值总是不大于或不小于其父节点的值 堆总是一棵完全二叉树。 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 childchild parent*21; 然后继续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 操作调整堆使剩余部分保持堆的结构。每次交换后堆的大小减少1end 变量逐渐减小直到所有元素排好序。 结束条件当 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 (parent0) {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 类来实现这一数据结构。此外我们还手动实现了基于数组的优先级队列深入了解了堆的构建、插入、删除等操作的细节掌握了如何利用堆的性质高效地完成优先级队列的功能。
优先级队列的实现方式多种多样堆是最常用且高效的方式适用于大多数需求。而在一些特定应用中可能还会采用其他的数据结构来优化性能或者适应特定场景的需求。通过本篇博客的学习您不仅能够理解优先级队列的工作原理还能够在实际开发中灵活应用这一数据结构来解决复杂的任务调度、图遍历和排序问题。
未来随着技术的不断发展优先级队列在新的应用场景中的作用将愈发重要。例如在人工智能、机器学习、实时系统等领域优先级队列的高效性和灵活性将为我们提供更多的解决方案。
希望这篇文章能帮助你更好地理解优先级队列并能够将其应用到实际项目中。如果你对优先级队列或其他数据结构有任何疑问欢迎随时交流探讨
