线性表--08---优先队列-北京尧图网络

文章目录优先队列背景:分类:1.最大优先队列树--07---堆的实现最大优先队列API设计代码实现测试:2.最小优先队列最大堆最小堆最小优先队列API设计代码实现测试:3.索引优先队列实现思路步骤一步骤二步骤三方法qp数组实际是记录, 原items数组每个位置的索引, 根据存入的value值排序后,索引的位置索引优先队列API设计代码实现测试优先队列背景:普通的队列是一种先进先出的数据结构元素在队列尾追加而从队列头删除。在某些情况下我们可能需要找出队列中的最大值或者最小值例如使用一个队列保存计算机的任务一般情况下计算机的任务都是有优先级的我们需要在这些计算机的任务中找出优先级最高的任务先执行执行完毕后就需要把这个任务从队列中移除。普通的队列要完成这样的功能需要每次遍历队列中的所有元素比较并找出最大值效率不是很高这个时候我们就可以使用一种特殊的队列来完成这种需求优先队列。分类:最大优先队列可以获取并删除队列中最大的值最小优先队列可以获取并删除队列中最小的值1.最大优先队列我们之前学习过堆而堆这种结构是可以方便的删除最大的值所以接下来我们可以基于堆区实现最大优先队列树–07—堆的实现最大优先队列API设计代码实现packagemain.java.Algorithms.priority;publicclassMaxPriorityQueueTextendsComparableT{//存储堆中的元素privateT[]items;//记录堆中元素的个数privateintN;publicMaxPriorityQueue(intcapacity){this.items(T[])newComparable[capacity1];this.N0;}//获取队列中元素的个数publicintsize(){returnN;}//判断队列是否为空publicbooleanisEmpty(){returnN0;}//判断堆中索引i处的元素是否小于索引j处的元素privatebooleanless(inti,intj){returnitems[i].compareTo(items[j])0;}//交换堆中i索引和j索引处的值privatevoidexch(inti,intj){Ttmpitems[i];items[i]items[j];items[j]tmp;}//往堆中插入一个元素publicvoidinsert(Tt){items[N]t;swim(N);}//删除堆中最大的元素,并返回这个最大元素publicTdelMax(){Tmaxitems[1];exch(1,N);N--;sink(1);returnmax;}//使用上浮算法使索引k处的元素能在堆中处于一个正确的位置privatevoidswim(intk){while(k1){if(less(k/2,k)){exch(k/2,k);}kk/2;}}//使用下沉算法使索引k处的元素能在堆中处于一个正确的位置privatevoidsink(intk){while(2*kN){intmax;if(2*k1N){if(less(2*k,2*k1)){max2*k1;}else{max2*k;}}else{max2*k;}if(!less(k,max)){break;}exch(k,max);kmax;}}}测试:packagemain.java.Algorithms.priority;publicclassMaxPriorityQueueTest{publicstaticvoidmain(String[]args){//创建优先队列MaxPriorityQueueStringqueuenewMaxPriorityQueue(10);//往队列中存储元素queue.insert(A);queue.insert(B);queue.insert(C);queue.insert(D);queue.insert(E);queue.insert(F);queue.insert(G);//通过循环从队列中获取最大的元素while(!queue.isEmpty()){Stringmaxqueue.delMax();System.out.print(max );}}}2.最小优先队列最小优先队列实现起来也比较简单我们同样也可以基于堆来完成最小优先队列最大堆我们前面学习堆的时候堆中存放数据元素的数组要满足都满足如下特性最大的元素放在数组的索引1处。每个结点的数据总是大于等于它的两个子结点的数据。最小堆最小的元素放在数组的索引1处。每个结点的数据总是小于等于它的两个子结点的数据。最小优先队列API设计代码实现packagemain.java.Algorithms.priority;publicclassMinPriorityQueueTextendsComparableT{//存储堆中的元素privateT[]items;//记录堆中元素的个数privateintN;publicMinPriorityQueue(intcapacity){this.items(T[])newComparable[capacity1];this.N0;}//获取队列中元素的个数publicintsize(){returnN;}//判断队列是否为空publicbooleanisEmpty(){returnN0;}//判断堆中索引i处的元素是否小于索引j处的元素privatebooleanless(inti,intj){returnitems[i].compareTo(items[j])0;}//交换堆中i索引和j索引处的值privatevoidexch(inti,intj){Ttmpitems[i];items[i]items[j];items[j]tmp;}//往堆中插入一个元素publicvoidinsert(Tt){items[N]t;swim(N);}//删除堆中最小的元素,并返回这个最小元素publicTdelMin(){Tminitems[1];exch(1,N);N--;sink(1);returnmin;}//使用上浮算法使索引k处的元素能在堆中处于一个正确的位置privatevoidswim(intk){//通过循环比较当前结点和其父结点的大小while(k1){if(less(k,k/2)){exch(k,k/2);}kk/2;}}//使用下沉算法使索引k处的元素能在堆中处于一个正确的位置privatevoidsink(intk){//通过循环比较当前结点和其子结点中的较小值while(2*kN){//1.找到子结点中的较小值intmin;if(2*k1N){if(less(2*k,2*k1)){min2*k;}else{min2*k1;}}else{min2*k;}//2.判断当前结点和较小值的大小if(less(k,min)){break;}exch(k,min);kmin;}}}测试:packagemain.java.Algorithms.priority;publicclassMinPriorityQueueTest{publicstaticvoidmain(String[]args){//创建最小优先队列对象MinPriorityQueueStringqueuenewMinPriorityQueueString(10);//往队列中存数据queue.insert(G);queue.insert(F);queue.insert(E);queue.insert(D);queue.insert(C);queue.insert(B);queue.insert(A);//通过循环获取最小优先队列中的元素while(!queue.isEmpty()){Stringminqueue.delMin();System.out.print(min );}}}3.索引优先队列在之前实现的最大优先队列和最小优先队列他们可以分别快速访问到队列中最大元素和最小元素但是他们有一个缺点就是没有办法通过索引访问已存在于优先队列中的对象并更新它们。为了实现这个目的在优先队列的基础上学习一种新的数据结构索引优先队列。接下来我们以最小索引优先队列举列。实现思路步骤一存储数据时给每一个数据元素关联一个整数例如insert(int k,T t),我们可以看做k是t关联的整数那么我们的实现需要通过k这个值快速获取到队列中t这个元素此时有个k这个值需要具有唯一性。最直观的想法就是我们可以用一个T[] items数组来保存数据元素在insert(int k,T t)完成插入时可以把k看做是items数组的索引把t元素放到items数组的索引k处这样我们再根据k获取元素t时就很方便了直接就可以拿到items[k]即可。步骤二步骤一完成后的结果虽然我们给每个元素关联了一个整数并且可以使用这个整数快速的获取到该元素但是items数组中的元素顺序是随机的并不是堆有序的所以为了完成这个需求我们可以增加一个数组int[]pq,来保存每个元素在items数组中的索引pq数组需要堆有序也就是说pq[1]对应的数据元素items[pq[1]]要小于等于pq[2]和pq[3]对应的数据元素items[pq[2]]和items[pq[3]]。步骤三通过步骤二的分析我们可以发现其实我们通过上浮和下沉做堆调整的时候其实调整的是pq数组。如果需要对items中的元素进行修改比如让items[0]“H”,那么很显然我们需要对pq中的数据做堆调整而且是调整pq[9]中元素的位置。但现在就会遇到一个问题我们修改的是items数组中0索引处的值如何才能快速的知道需要挑中pq[9]中元素的位置呢最直观的想法就是遍历pq数组拿出每一个元素和0做比较如果当前元素是0那么调整该索引处的元素即可但是效率很低。方法我们可以另外增加一个数组int[] qp,用来存储pq的逆序例如在pq数组中pq[1]6;那么在qp数组中把6作为索引1作为值结果是qp[6]1;qp数组实际是记录, 原items数组每个位置的索引, 根据存入的value值排序后,索引的位置索引优先队列API设计代码实现packagemain.java.Algorithms.priority;publicclassIndexMinPriorityQueueTextendsComparableT{//存储堆中的元素privateT[]items;//保存每个元素在items数组中的索引pq数组需要堆有序privateint[]pq;//保存qp的逆序pq的值作为索引pq的索引作为值privateint[]qp;//记录堆中元素的个数privateintN;publicIndexMinPriorityQueue(intcapacity){this.items(T[])newComparable[capacity1];this.pqnewint[capacity1];this.qpnewint[capacity1];this.N0;//默认情况下队列中没有存储任何数据让qp中的元素都为-1for(inti0;iqp.length;i){qp[i]-1;}}//获取队列中元素的个数publicintsize(){returnN;}//判断队列是否为空publicbooleanisEmpty(){returnN0;}//判断堆中索引i处的元素是否小于索引j处的元素privatebooleanless(inti,intj){returnitems[pq[i]].compareTo(items[pq[j]])0;}//交换堆中i索引和j索引处的值privatevoidexch(inti,intj){//交换pq中的数据inttmppq[i];pq[i]pq[j];pq[j]tmp;//更新qp中的数据qp[pq[i]]i;qp[pq[j]]j;}//判断k对应的元素是否存在publicbooleancontains(intk){returnqp[k]!-1;}//最小元素关联的索引publicintminIndex(){returnpq[1];}//往队列中插入一个元素,并关联索引ipublicvoidinsert(inti,Tt){//判断i是否已经被关联如果已经被关联则不让插入if(contains(i)){return;}//元素个数1N;//把数据存储到items对应的i位置处items[i]t;//把i存储到pq中pq[N]i;//通过qp来记录pq中的iqp[i]N;//通过堆上浮完成堆的调整swim(N);}//删除队列中最小的元素,并返回该元素关联的索引publicintdelMin(){//获取最小元素关联的索引intminIndexpq[1];//交换pq中索引1处和最大索引处的元素exch(1,N);//删除qp中对应的内容qp[pq[N]]-1;//删除pq最大索引处的内容pq[N]-1;//删除items中对应的内容items[minIndex]null;//元素个数-1N--;//下沉调整sink(1);returnminIndex;}//删除索引i关联的元素publicvoiddelete(inti){//找到i在pq中的索引intkqp[i];//交换pq中索引k处的值和索引N处的值exch(k,N);//删除qp中的内容qp[pq[N]]-1;//删除pq中的内容pq[N]-1;//删除items中的内容items[k]null;//元素的数量-1N--;//堆的调整sink(k);swim(k);}//把与索引i关联的元素修改为为tpublicvoidchangeItem(inti,Tt){//修改items数组中i位置的元素为titems[i]t;//找到i在pq中出现的位置intkqp[i];//堆调整sink(k);swim(k);}//使用上浮算法使索引k处的元素能在堆中处于一个正确的位置privatevoidswim(intk){while(k1){if(less(k,k/2)){exch(k,k/2);}kk/2;}}//使用下沉算法使索引k处的元素能在堆中处于一个正确的位置privatevoidsink(intk){while(2*kN){//找到子结点中的较小值intmin;if(2*k1N){if(less(2*k,2*k1)){min2*k;}else{min2*k1;}}else{min2*k;}//比较当前结点和较小值if(less(k,min)){break;}exch(k,min);kmin;}}}测试packagemain.java.Algorithms.priority;publicclassIndexMinPriorityQueueTest{publicstaticvoidmain(String[]args){//创建索引最小优先队列对象IndexMinPriorityQueueStringqueuenewIndexMinPriorityQueue(10);//往队列中添加元素queue.insert(0,A);queue.insert(1,C);queue.insert(2,F);//测试修改queue.changeItem(2,B);//测试删除while(!queue.isEmpty()){intindexqueue.delMin();System.out.print(index );}}}

线性表--08---优先队列

相关推荐

SeetaFace6实战指南：全栈人脸识别工具包从检测到活体的落地路径

WPF ComboBox数据绑定五种实战方式与避坑指南

Web开发必备：Redis核心原理、实战场景与性能优化全解析

更多资讯

想考电工证如何学习保姆级教程：学历不高怕报不上名？别慌，手把手教你

沧州电工证报考时间怎么考

低压电工证科目二点动全流程办理指南：通过率揭秘

电工证查询西宁列表多久拿证：工地太忙根本没时间复习考试？教你快速拿证攻略

枣阳低压电工证过期了不知道怎么复审延期？网上查询是关键

特种作业技能操作证实操考试考什么

今日更新

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？

相关推荐

SeetaFace6实战指南：全栈人脸识别工具包从检测到活体的落地路径

WPF ComboBox数据绑定五种实战方式与避坑指南

Web开发必备：Redis核心原理、实战场景与性能优化全解析

更多资讯

想考电工证如何学习保姆级教程：学历不高怕报不上名？别慌，手把手教你

沧州电工证报考时间怎么考

低压电工证科目二点动全流程办理指南：通过率揭秘

电工证查询西宁列表多久拿证：工地太忙根本没时间复习考试？教你快速拿证攻略

枣阳低压电工证过期了不知道怎么复审延期？网上查询是关键

特种作业技能操作证实操考试考什么

今日更新

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗 良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗 良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？

新疆电工作业干活累吗良心建议助你避开考不过的坑

新疆电工作业干活累吗良心建议助你避开考不过的坑