首页 > 代码库 > 优先队列用法
优先队列用法
优先队列用法（即百家之所长写的)
在优先队列中，优先级高的元素先出队列。
标准库默认使用元素类型的<操作符来确定它们之间的优先级关系。
(1)：
如果我们要把元素从小到大输出怎么办呢？
这时我们可以传入一个比较函数，使用functional.h函数对象作为比较函数。
它的模板声明带有3个参数：
priority_queue<Type,Container,Functional>
其中
Type为数据类型；
Container必须是用数组实现的容器(保存数据)，比如vector,deque但不能用list；
Functional为元素的比较方式。
STL里 面 默 认 用 的 是 vector。比 较 方 式 默 认 用 operator<, 所 以 如 果 你 把 后 面 两个参数省略的话，优先队列就是大顶堆，即头元素最大。
1 #include<iostream> 2 3 #include<functional> 4 5 #include<queue> 6 7 using namespace std; 8 9 int main()10 11 {12 13 const int len=5;14 15 int i;16 17 int a[len]={3,5,9,6,2};18 19 20 21 priority_queue<int> qi;22 23 for(i=0;i<len;i++)24 25 qi.push(a[i]);26 27 for(i=0;i<len;i++)28 29 {30 31 cout<<qi.top()<<" ";32 33 qi.pop();34 35 }36 37 return 0;38 39 }
例1输出结果为：9 6 5 3 2
小顶堆：
则一般要把模板的3个参数都带进去。
STL里面定义了一个仿函数greater<>，对于基本类型可以用这个仿函数声明
小顶堆：
priority_queue<int, vector<int>, greater<int> >qi2
故示例2中输出结果为：2 3 5 6 9
(2)：
自定义优先级一：
struct node
{
friend bool operator< (node n1, node n2)
{
return n1.priority < n2.priority;
}
int priority;
int value;
};
在该结构中，value为值，priority为优先级。
通过自定义operator<操作符来比较元素中的优先级。
//代码清单
1 #include<iostream> 2 3 #include<functional> 4 5 #include<queue> 6 7 using namespace std; 8 9 struct node10 11 {12 13 friend bool operator< (node n1, node n2)14 15 {16 17 return n1.priority < n2.priority;18 19 }20 21 int priority;22 23 int value;24 25 };26 27 int main()28 29 {30 31 const int len = 5;32 33 int i;34 35 36 37 priority_queue<node> qn;38 39 node b[len]={{6,1},{9,5},{2,3},{8,2},{1,4}};40 41 /* b[0].priority = 6; b[0].value = http://www.mamicode.com/1;>42 43 b[1].priority = 9; b[1].value = http://www.mamicode.com/5;>44 45 b[2].priority = 2; b[2].value = http://www.mamicode.com/3;>46 47 b[3].priority = 8; b[3].value = http://www.mamicode.com/2;>48 49 b[4].priority = 1; b[4].value = http://www.mamicode.com/4;*/50 51 52 53 54 55 for(i = 0; i < len; i++)56 57 qn.push(b[i]);58 59 cout<<"优先级"<<‘\t‘<<"值"<<endl;60 61 for(i = 0; i < len; i++)62 63 {64 65 cout<<qn.top().priority<<‘\t‘<<qn.top().value<<endl;66 67 qn.pop();68 69 }70 71 return 0;72 73 }
输出结果为：
优先级 值
9 5
8 2
6 1
2 3
1 4
自定义优先级二：
1 #include<stdio.h> 2 3 #include<functional> 4 5 #include<queue> 6 7 #include<vector> 8 9 using namespace std; 10 11 12 13 struct cmp1 14 15 { 16 17 bool operator()(int &a,int &b) 18 19 { 20 21 return a>b;//最小值优先 22 23 } 24 25 }; 26 27 struct cmp2 28 29 { 30 31 bool operator()(int &a,int &b) 32 33 { 34 35 return a<b;//最大值优先 36 37 } 38 39 }; 40 41 struct number1 42 43 { 44 45 int x; 46 47 bool operator<(const number1&a)const 48 49 { 50 51 return x>a.x;//最小值优先 52 53 } 54 55 }; 56 57 struct number2 58 59 { 60 61 int x; 62 63 bool operator<(const number2&a)const 64 65 { 66 67 return x<a.x;//最大值优先 68 69 } 70 71 }; 72 73 int a[]={14,10,56,7,83,22,36,91,3,47,72,0}; 74 75 number1 num1[]={14,10,56,7,83,22,36,91,3,47,72,0}; 76 77 number2 num2[]={14,10,56,7,83,22,36,91,3,47,72,0}; 78 79 80 81 int main() 82 83 { 84 85 int i=0; 86 87 priority_queue<int,vector<int>,cmp1>que1;//最小值优先 88 89 priority_queue<int,vector<int>,cmp2>que2;//最大值优先 90 91 priority_queue<int,vector<int>,less<int> >que4;//最大值优先 92 93 priority_queue<number1>que5;//最小值优先 94 95 priority_queue<number2>que6;//最大值优先 96 97 98 99 for(i=0;a[i];i++)100 101 {102 103 que1.push(a[i]);104 105 que2.push(a[i]);106 107 que4.push(a[i]);108 109 }110 111 for(i=0;num1[i].x;i++)112 113 que5.push(num1[i]);114 115 for(i=0;num2[i].x;i++)116 117 que6.push(num2[i]);118 119 120 121 printf("采用结构体自定义优先级方式一：\n(priority_queue<int,vector<int>,cmp1/cmp2>que1;)\n");122 123 printf("Queue 1\n");124 125 while(!que1.empty())126 127 {128 129 printf("%3d",que1.top());130 131 que1.pop();132 133 }134 135 printf("\n");136 137 printf("Queue 2\n");138 139 while(!que2.empty())140 141 {142 143 printf("%3d",que2.top());144 145 que2.pop();146 147 }148 149 printf("\n\n");150 151 152 153 printf("采用头文件\"functional\"内定义优先级：\n(priority_queue<int,vector<int>,less<int> >que4;)\n");154 155 printf("Queue 4:\n");156 157 while(!que4.empty())158 159 {160 161 printf("%3d",que4.top());162 163 que4.pop();164 165 }166 167 printf("\n\n");168 169 170 171 printf("采用结构体自定义优先级方式二：\n(priority_queue<number1/number2>que;)\n");172 173 printf("Queue 5:\n");174 175 while(!que5.empty())176 177 {178 179 printf("%3d",que5.top());180 181 que5.pop();182 183 }184 185 printf("\n");186 187 188 189 printf("Queue 6:\n");190 191 while(!que6.empty())192 193 {194 195 printf("%3d",que6.top());196 197 que6.pop();198 199 }200 201 printf("\n");202 203 return 0;204 205 }
优先队列用法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。