C++优先队列
优先队列的实现是一个大根堆,所以每次 push(x)/pop() 操作的时间复杂度是 O(logn),log以2为底,n是该优先队列中的元素个数 ? 优先队列中的元素一定要定义小于号,C++中自带的类型 int,char 等已经定义好小于号了 ? http://www.luyixian.cn/news_show_13320.aspx 在图搜索时经常 用到宽搜来求得最短路,而有这样一类题目在求得最短路时又要使得?花费(cost可以是任意一种要求,比如改变方向的次数或者其他)最小?,这样每次队列中出队的元素就要满足元素优先出队。STL中的?priority_queue(优先队列)?就可以解决这样的问题。这样的模板类在头文件中,内部实现是?堆。 使用细节
定义priority_queue对象的示例代码如下: priority_queue<int> q1; priority_queue< pair<int,int> > q2; // 注意在两个尖括号之间 一定要留空格。 priority_queue<int,vector<int>,greater<int> > q3; // 定义小的先出队 对于比较算子:如果是基本数据类型,或已定义了比较运算符的类,可以直接用STL的less 算子和greater算子——默认为使用less算子,即小的往前排,大的先出队。 ? #include <iostream> #include <deque> // 双端队列 #include <queue> // 单端队列 using namespace std; struct Stu { int age; const char* name; }; struct stuless { bool operator()(const struct Stu _left,const struct Stu _right) { return _left.age < _right.age; } }; int main() { priority_queue<Stu,vector<Stu>,stuless> myPri; Stu s1 = { 33,"abcd" }; Stu s2 = { 22,"edgh" }; Stu s3 = { 24,"vin" }; Stu s4 = { 55,"vin" }; myPri.push(s1); myPri.push(s2); myPri.push(s3); myPri.push(s4); while (!myPri.empty()) { Stu tmp = myPri.top(); cout << tmp.name << ": " << tmp.age << endl; myPri.pop(); } cin.get(); return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |