概念
C++优先队列类似队列,具有队列的所有特性,包括基本操作,只是在这基础上添加了内部的一个排序,它本质是一个堆实现的,使优先级高的排在前面,优先出列。
头文件
1 |
名字空间
1 | std |
构造函数
定义:
1 | priority_queue<Type, Container, Functional> |
Type
就是数据类型,Container
就是容器类型(Container
必须是用数组实现的容器,比如vector,deque
等等,但不能用 list
。STL
里面默认用的是vector
),Functional
就是比较的方式,当需要用自定义的数据类型时才需要传入这三个参数,使用基本数据类型时,只需要传入数据类型,默认是大顶堆。
基本类型构造:
如果我们把后面俩个参数缺省的话,优先队列就是大根堆,队头元素最大。1
2
3
4
5
6//大根堆,降序队列
priority_queue<int> Q1;
priority_queue <int,vector<int>,less<int> > Q2;
// 小根堆,升序队列 ↓这里一定要有空格,不然成了右移运算符
priority_queue<int, vector<int>, greater<int> > Q3;
greater
和less
是std
实现的两个仿函数(就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator()
,这个类就有了类似函数的行为,就是一个仿函数类了)
结构体构造:
1 |
|
常用函数
empty
语法:
1 | bool empty(); |
empty()
函数返回真(true
)如果优先队列为空,否则返回假(false
)。
pop
语法:
1 | void pop(); |
pop()
函数删除优先队列中的第一个元素。
push
语法:
1 | void push( const TYPE &val ); |
push()
函数添加一个元素到优先队列中,值为val
。
size
语法:
1 | size_type size(); |
size()
函数返回优先队列中存储的元素个数。
top
语法:
1 | TYPE &top(); |
top()
返回一个引用,指向优先队列中有最高优先级的元素。注意只有pop()
函数删除一个元素。