做足球直播网站,wordpress默认邮件文件,网站管理后台密码忘记了,哪个网站可以免费做简历目录
1.初识优先级队列
库中的实现
使用优先级队列
2.优先级队列的实现
3.仿函数
利用仿函数实现的优先级队列
迭代器区间构造#xff08;建堆#xff09; 1.初识优先级队列 如果我们给每个元素都分配一个数字来标记其优先级#xff0c;不妨设较小的数字具有较…
目录
1.初识优先级队列
库中的实现
使用优先级队列
2.优先级队列的实现
3.仿函数
利用仿函数实现的优先级队列
迭代器区间构造建堆 1.初识优先级队列 如果我们给每个元素都分配一个数字来标记其优先级不妨设较小的数字具有较高的优先级这样我们就可以在一个集合中访问优先级最高的元素并对其进行查找和删除操作了。这样我们就引入了优先级队列 这种数据结构。 优先级队列priority queue 是0个或多个元素的集合每个元素都有一个优先权对优先级队列执行的操作有
优先队列也是一种抽象数据类型。优先队列中的每个元素都有优先级而优先级高或者低的将会先出队而优先级相同的则按照其在优先队列中的顺序依次出队。
库中的实现 对于库中的实现参数来说可以看到也是给了容器模版适配器还给了缺省参数为vector。
其次有一个compare参数默认下给了缺省参数less的一个对象实际上还有一个对象greater这决定了优先级是较大的优先less还是较小的优先(greater)。
注意这里与库中的sort的排序顺序是相反的。 对于接口我们可以看到它与栈的结构很像其次与堆的结构的结构也很像我们在数据结构部分知道取堆顶元素再结合优先级队列的概念寻找元素的大小仔细想想那么实际上优先级队列是一个堆的结构利用建大堆的方式获取最大的元素等。
实际上对于适配器我们不仅仅只是数组我们也可以传双端队列作为适配器也是可以的。
使用优先级队列
简单的使用下我们可以看到这里在默认的情况下较大的数一个个输出故默认情况下这里给的是大堆取堆顶元素便是最大的删除元素-我们调换堆顶的元素与末尾的元素向下调整。
因为是堆的结构故我们可以知道优先级队列插入删除的时间线复杂度为logN,
void test()
{priority_queueint,vectorint p;//取大的 大堆//priority_queueint,vectorint ,greaterint p;//取小的 小堆//入队 p.push(1);p.push(2);p.push(3);p.push(4);p.push(5);p.push(6);//打印并出队 while(!p.empty()){coutp.top();p.pop();} }
通过给出参数的不同我们可以改变优先级是大或是小。
2.优先级队列的实现
明白了优先级队列的结构之后我们自己也可以简单实现一下优先级队列。 这里我们先不知道compare是个啥我们先实现出默认的大堆结构也就是大的优先然后就是给出类型模版和适配器。
//默认实现大的优先级队列
namespace mypriority_queue
{templateclass T,class Container vectorT class priority_queue{public://入优先级队列本质上就是建大堆 void push(cosnt T x){//尾插_con.push_back(x); //向上调整 adjust_up(_con.size()-1);//从尾插的位置想上调整 尾插前size(),故减一 }void adjust_up(int child){size_t parent(child-1)/2;while(child0){if(_con[child]_con[parent]childparent){swap(_con[child],_con[parent]); childparent;paren(parent-1)/2;} }else{break;} }//出优先级队列删除堆顶元素(先交换在尾删在向下调整)void pop(){swap(_con[_con.size()-1],_con[0]);_con.pop_back();adjust_down(0);} void adjust_down(int parent){size_t childparent*21;while(parent_con.size()){if(child1_con.size()_con[chid1]a[parent]){child; }if(_con[chid]a[parent]){swap(_con[child],_con[parent]);parentchild;childchild*21;}}else{break;}}const T top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;}}
其中拷贝构造等都不需要我们实现了系统在调用时会调用我们的容器里的。
3.仿函数
上面已经实现了优先级队列以较大的为优先那么较小的我们也可以在实现一个改变一下向上调整与向上调整的比较符号为小于就是以小的为优先也就是小堆。
可是我们在用的时候没必要为两份差不多相同的代码搞两个的容器来让我们调用需要大的用大的要小的用小的那么有没有办法可以通过参数的不同的就能直接改变函数成为大堆或小堆即通过参数不同改变函数。
c提供了仿函数来实现
仿函数(functor)就是使一个类的使用看上去像一个函数。其实本质就是类中实现一个重载(),operator()这个类就有了类似函数的行为就是一个仿函数类了。
如下
class Less
{
public:bool operator()(int x,int y){return xy;}
};
int main()
{Less less;coutless(2,3);coutless.operator()(2,3);//两者本质一样 return 0;
}
实际上本质上是一个类类中实现了重载()简写的时候本质上是对象调用方法但看起来像函数调用。
通过仿函数我们就可以实现利用对象调用函数重载的越多对象可以调用的也就多了以这种方式优先级队列可以通过传对象的方法来实现大的优先级和小的优先级都可以调用
利用仿函数实现的优先级队列
一般使用的时候我们都是将模版与重载结合起来。
改变传参的仿函数就是改变比较的符号在通过对象调用
templateclass Tclass Less//大堆
{
public:bool operator()(const Tx,const Ty){return xy;}
};
templateclass Tclass Greater//小堆
{
public:bool operator()(const Tx,const Ty){return xy;}
};
namespace mypriority_queue
{templateclass T,class Container vectorT ,class compareLessT class priority_queue{compare com;public://入优先级队列本质上就是建大堆 void push(const T x){//尾插_con.push_back(x); //向上调整 adjust_up(_con.size()-1);//从尾插的位置想上调整 尾插前size(),故减一 }void adjust_up(int child){int parent(child-1)/2;while(child0){if(com(_con[child],_con[parent])childparent){swap(_con[child],_con[parent]); childparent;parent(parent-1)/2;} }else{break;} }//出优先级队列删除堆顶元素(先交换在尾删在向下调整)void pop(){swap(_con[_con.size()-1],_con[0]);_con.pop_back();adjust_down(0);} void adjust_down(int parent){size_t childparent*21;while(parent_con.size()){if(_con.sizechild1com(_con[child1],a[parent])){child; }if(com(_con[child],a[parent])){swap(_con[child],_con[parent]);parentchild;childchild*21;}}else{break;}}const T top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;}}
对于c提供的仿函数我们也可以用此替换函数指针函数指针在实际的应用上比较麻烦我们可以利用仿函数替换他。
那么现在我们就知道在库中就已经有实现的less和greater,我们可以直接调用库中的。 当然除了库中提供的的less与greater外我们还可以实现自己所需要的类型的比较比如对Data类型的数据作比较我们可以实现自己的仿函数在通过参数传递用来实现Data类比较。
其次算法库中也提供了许多对于堆的一些判断接口等 可以看到有堆排序建堆出入堆等接口。
迭代器区间构造建堆
在原有基础上添加了另一种初始化的方法利用迭代器区间来直接完成建堆
priority_queue(){} //迭代器区间初始化template class Inputiteratorpriority_queue(Inputoriterator first,Inputoriterator last):_con(first,last)//容器提供有迭代器区间初始化 {//建堆初始化之后--向下调整 for(int i(_con.size()-2)/2;i0;i--){//堆从最后一个parent开始调整 adjust_down(i);}}
因为容器本身具有迭代器区间初始化我们只需要再次调整即可此外因为我们自己写入了带有参数的构造函数那么就需要再补充一个本身的无参构造即可。
