杭州网站推广公司,企业建站设计,郑州网站建设msgg,申请商标注册需要什么资料一、问题概述
优先级队列的定义#xff1a; 优先级队列不同于普通的队列#xff0c;普通的队列具有先进先出的原则#xff0c;而优先级队列是选择优先级最高的先出队。那么#xff0c;如何模拟实现优先级队列呢#xff1f;在这里#xff0c;我们将较大的值作为优先级较高…一、问题概述
优先级队列的定义 优先级队列不同于普通的队列普通的队列具有先进先出的原则而优先级队列是选择优先级最高的先出队。那么如何模拟实现优先级队列呢在这里我们将较大的值作为优先级较高的。 二、解决思路 1用插入排序的思想将它们按由大到小也可由小到大排好序再push到队列中那么队列中的队首元素便是优先级最高的取其front便可得到优先级最高的值。 此时push的时间复杂度为O1,pop的时间复杂度为ON,Top的时间复杂度为O1. 2用选择排序的思想选择出值最大的那个元素将其push到队列中再取次大的push到队列中依次下去将所有值push到队列中那么队列中的队首元素便是优先级最高的取其front便可得到优先级最高的值。 此时push的时间复杂度为ON,pop的时间复杂度为O1,Top的时间复杂度为ON. 那么根据时间复杂度来看两种算法哪一个更好呢
解析一下如果不考虑取Top()比较插入排序和选择排序
插入排序push时间复杂度为O1pop时如果无序的话它是ON,但是如果本身是有序的话pop的时间复杂度就为O1它是可变的分最好最坏
但是选择排序就不一样了它的push的复杂度永远都为ONpop的时间复杂度为O1 综上所述插入排序的思想实现优先级队列更好。
下面把两种优先级队列都实现一下吧~~ 三、实现代码 //插入排序实现优先级队列
#pragma once
#includeiostream
using namespace std;
#includequeue
#includeassert.htemplatetypename T
T QueuePriority(T *arr1,size_t size)
{assert(arr1);queueT q;T arr2[7] {0};arr2[0] arr1[0];for(size_t i 1; i size; i){if(arr2[i-1] arr1[i]){arr2[i] arr1[i];}else{size_t j 0;for(j i-1; j 0; --j){if(arr2[j] arr1[i]){arr2[j1] arr2[j];}else{break;}}arr2[j1] arr1[i];}}for(int k size-1; k 0; k--){q.push(arr2[k]);}return q.front();
}void FunTest()
{int arr1[] {1,3,5,4,2,6,0};char arr2[] {a,d,b,c};size_t size sizeof(arr1)/sizeof(arr1[0]);size_t size1 sizeof(arr2)/sizeof(arr2[0]);coutQueuePriorityint(arr1,size)endl;coutQueuePrioritychar(arr2,size1)endl;
}int main()
{FunTest();return 0;
}//用选择排序实现优先级队列
#pragma once
#includeiostream
using namespace std;
#includequeue
#includeassert.htemplatetypename T
T QueuePriority(T *arr1,size_t size)
{assert(arr1);queueT q;for(size_t i 0; i size; i){T max i; for(size_t j i1;j size; j){if(arr1[max] arr1[j]){max j;}}swap(arr1[max],arr1[i]);q.push(arr1[i]);}return q.front();
}void FunTest()
{int arr1[] {1,3,5,4,2,6,0};char arr2[] {a,d,b,c};size_t size sizeof(arr1)/sizeof(arr1[0]);size_t size1 sizeof(arr2)/sizeof(arr2[0]);coutQueuePriorityint(arr1,size)endl;coutQueuePrioritychar(arr2,size1)endl;
}int main()
{FunTest();return 0;
}
