优先队列的实现常选用二叉堆。
优先队列的基本操作：
.top 访问队头元素
.empty 队列是否为空
.size 返回队列内元素个数
.push 插入元素到队尾 (并排序)
.pop 弹出队头元素
.swap 交换内容
优先队列的声明：
priority_queue<type,container,function>
用该形式的代码声明优先队列
type：数据类型
container：实现优先队列的底层容器
function：优先队列的比较方式
声明的后面必须是less<int> >q，不能是less<int>>q
priority_queue<int> q;//这样是简化的优先队列，出队形式单调递减
priority_queue<int,vector<int>, less<int> >q;//该形式同样也是单调递减出队（less递减）
priority_queue<int,vector<int>, greater<int> >q;//该形式是单调递增出队（greater递增）
下面是pair两个变量的声明
priority_queue<pair<int, int> > q;//这个也是从大到小递减出队，并且优先比较第一个数，其次才是第二个数
//如果要改成从小到大的递增顺序出队可以写成
priority_queue<pair<int,int>, vector<pair<int,int> >,greater<pair<int,int> > > q;
//pair的定义
pair<int, int> a(1, 2);
这样就得到了一个1，2的叫做a的pair
除此之外可以用自定义的struct声明队列
- 重载运算符写法
struct node
{
int a, b;
bool operator<(const node& y) const
{
return a < y.a;
}
};
...
...
priority_queue<node> q;
- 重写伪函数写法
struct node
{
inta, b;
};
struct cmp
{
bool operator() (node a, node b)
{
return a.x < b.x;
}
};
...
...
priority_queue<node, vector<node>, cmp> q;
