【C++】priority_queue的用法(模板参数的实例)

本文主要是介绍【C++】priority_queue的用法(模板参数的实例)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【C++】priority_queue的用法

使用priority_queue需要包含头文件 <queue>；
其模板申明带3个参数：priority_queue<Type, Container, Functional>，其中Type 为数据类型，Container为保存数据的容器，Functional 为元素比较方式。
其中Container必须是使用数组实现的容器，例如vector、dequeue等，不能使用list。

大根堆

该函数使用，后两个参数可以缺省，例如可以声明这样一个优先级队列：priority_queue<int> q，此时元素的比较方式默认用operator<，优先级队列就是大根堆，队头元素最大。

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main(){priority_queue<pair<int,int> > coll;pair<int,int> a(3,4);pair<int,int> b(3,5);pair<int,int> c(4,3);coll.push(c);coll.push(b);coll.push(a);while(!coll.empty()){cout<<coll.top().first<<"\t"<<coll.top().second<<endl;coll.pop();}return 0;
}//-------------------------------------
//来源于https://www.cnblogs.com/shona/p/12163381.html

小根堆

如果要实现小根堆，则需要把模板的3个参数都填写清除。STL里面定义了一个仿函数greater<>，基本类型可以用这个仿函数声明小顶堆。以下代代码返回pair的比较结果，先按照pair的first元素升序，first元素相等时，再按照second元素升序：

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int main(){priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > coll;pair<int,int> a(3,4);pair<int,int> b(3,5);pair<int,int> c(4,3);coll.push(c);coll.push(b);coll.push(a);while(!coll.empty()){cout<<coll.top().first<<"\t"<<coll.top().second<<endl;coll.pop();}return 0;
}
//------------------------------------------------------------
//来源于https://www.cnblogs.com/shona/p/12163381.html

自定义类型优先级队列

对于自定义类型优先级队列，则必须重载operator<函数。
例如，我们希望使用优先级队列实现A* 算法 priority_queue；

优先级队列的结构为(open list)：

std::priority_queue<std::pair<double, Node>, std::vector<std::pair<double, Node>>, greater> frontier;    // 创建为小根堆 open list

由于我们需要实现一个小根堆，所以三个参数都需要表明，模板中第一个参数表明单个元素的构成：std::pair<double, Node>，单个元素是有一个double数据和一个Node数据共同组成的，第二个参数表明优先级队列的存储容器构成std::vector<std::pair<double, Node>>，使用了一个vector来存储单个元素，第三个参数表明元素的比较方式。

struct greater{  constexpr bool operator() (const std::pair<double, Node>& lhs, const std::pair<double, Node>& rhs) const{//默认是less函数  //返回true时，lhs的优先级低于rhs的优先级（lhs排在rhs的后面）  return lhs.first > rhs.first;  }  
};

Node结构体构成：

struct Node{int x, y;Node( int a= 0, int b= 0 ):x(a), y(b) {}
};

通过这个方式，我们实现了一个优先级队列的A* 算法中的open list。

这篇关于【C++】priority_queue的用法(模板参数的实例)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---