标题:
STL容器之优先队列
[打印本页]
作者:
yuyang911220
时间:
2016-8-11 21:45
标题:
STL容器之优先队列
优先级队列,以前刷题的时候用的比较熟,现在竟然我只能记得它的关键字是priority_queue(太伤了)。在一些定义了权重的地方这个数据结构是很有用的。
先回顾队列的定义:队列(queue)维护了一组对象,进入队列的对象被放置在尾部,下一个被取出的元素则取自队列的首部。priority_queue特别之处在于,允许用户为队列中存储的元素设置优先级。这种队列不是直接将新元素放置在队列尾部,而是放在比它优先级低的元素前面。标准库默认使用<操作符来确定对象之间的优先级关系,所以如果要使用自定义对象,需要重载 < 操作符。
优先队列有两种,一种是最大优先队列;一种是最小优先队列;每次取自队列的第一个元素分别是优先级最大和优先级最小的元素。
1) 优先队列的定义
包含头文件:"queue.h", "functional.h"
可以使用具有默认优先级的已有数据结构;也可以再定义优先队列的时候传入自定义的优先级比较对象;或者使用自定义对象(数据结构),但是必须重载好< 操作符。
2) 优先队列的常用操作
优先级队列支持的操作
q.empty() 如果队列为空,则返回true,否则返回false
q.size() 返回队列中元素的个数
q.pop() 删除队首元素,但不返回其值
q.top() 返回具有最高优先级的元素值,但不删除该元素
q.push(item) 在基于优先级的适当位置插入新元素
其中q.top()为查找操作,在最小优先队列中搜索优先权最小的元素,在最大优先队列中搜索优先权最大的元素。q.pop()为删除该元素。优先队列插入和删除元素的复杂度都是O(lgn),所以很快
另外,在优先队列中,元素可以具有相同的优先权。
下面这个C例子,包含了几乎所有常见的优先队列用法。
[url=]
[/url]
#include<iostream>
#include
<functional>
#include
<queue>
#include
<vector>
using
namespace
std;
//
定义比较结构
struct
cmp1{
bool
operator
()(
int
&a,
int
&
b){
return
a>b;
//
最小值优先
}};
struct
cmp2{
bool
operator
()(
int
&a,
int
&
b){
return
a<b;
//
最大值优先
}};
//
自定义数据结构
struct
number1{
int
x;
bool
operator
< (
const
number1 &a)
const
{
return
x>a.x;
//
最小值优先
}};
struct
number2{
int
x;
bool
operator
< (
const
number2 &a)
const
{
return
x<a.x;
//
最大值优先
}};
int
a[]={
14
,
10
,
56
,
7
,
83
,
22
,
36
,
91
,
3
,
47
,
72
,
0
};number1 num1[]
={
14
,
10
,
56
,
7
,
83
,
22
,
36
,
91
,
3
,
47
,
72
,
0
};number2 num2[]
={
14
,
10
,
56
,
7
,
83
,
22
,
36
,
91
,
3
,
47
,
72
,
0
};
int
main(){ priority_queue
<
int
>que;
//
采用默认优先级构造队列
priority_queue
<
int
,vector<
int
>,cmp1>que1;
//
最小值优先
priority_queue<
int
,vector<
int
>,cmp2>que2;
//
最大值优先
priority_queue
<
int
,vector<
int
>,greater<
int
> >que3;
//
注意“>>”会被认为错误,
priority_queue<
int
,vector<
int
>,less<
int
> >que4;
///
/最大值优先
priority_queue
<number1>que5;
//
最小优先级队列
priority_queue<number2>que6;
//
最大优先级队列
int
i;
for
(i=
0
;a
;i++
){ que.push(a
); que1.push(a
); que2.push(a
); que3.push(a
); que4.push(a
); }
for
(i=
0
;num1
.x;i++
) que5.push(num1
);
for
(i=
0
;num2
.x;i++
) que6.push(num2
); printf(
"
采用默认优先关系:/n(priority_queue<int>que;)/n
"
); printf(
"
Queue 0:/n
"
);
while
(!
que.empty()){ printf(
"
%3d
"
,que.top()); que.pop(); } puts(
""
); puts(
""
); printf(
"
采用结构体自定义优先级方式一:/n(priority_queue<int,vector<int>,cmp>que;)/n
"
); printf(
"
Queue 1:/n
"
);
while
(!
que1.empty()){ printf(
"
%3d
"
,que1.top()); que1.pop(); } puts(
""
); printf(
"
Queue 2:/n
"
);
while
(!
que2.empty()){ printf(
"
%3d
"
,que2.top()); que2.pop(); } puts(
""
); puts(
""
); printf(
"
采用头文件/
"
functional/
"
内定义优先级:/n(priority_queue<int,vector<int>,greater<int>/less<int> >que;)/n
"
); printf(
"
Queue 3:/n
"
);
while
(!
que3.empty()){ printf(
"
%3d
"
,que3.top()); que3.pop(); } puts(
""
); printf(
"
Queue 4:/n
"
);
while
(!
que4.empty()){ printf(
"
%3d
"
,que4.top()); que4.pop(); } puts(
""
); puts(
""
); printf(
"
采用结构体自定义优先级方式二:/n(priority_queue<number>que)/n
"
); printf(
"
Queue 5:/n
"
);
while
(!
que5.empty()){ printf(
"
%3d
"
,que5.top()); que5.pop(); } puts(
""
); printf(
"
Queue 6:/n
"
);
while
(!
que6.empty()){ printf(
"
%3d
"
,que6.top()); que6.pop(); } puts(
""
);
return
0
;}
/*
运行结果 :
作者:
yuchengze
时间:
2016-8-19 15:14
好帖子,路过帮顶,占个沙发
欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)
Powered by Discuz! 7.0.0