priority_queue
优先队列(Priority Queues):顾名思义,一个有着优先级的队列。它是一种ADT,和队列的思想差不多—— 排队,数据结构中的队列是不能插队的,不能颠倒排队的顺序,而在优先队列里,先出队列的元素不是先进队列的元素,而是优先级高的元素,默认的优先级是数字大的数优先级高。当然用户是可自定义类型的,这样就必须为元素定义一个优先级。因为出队元素不是最先进队的元素,则出队的方法有queue的front() 变为top()。
priority_queue<Type, Container, Functional>
Type为数据类型, Container为保存数据的容器,Functional为元素比较方式。
如果不写后两个参数,那么容器默认用的是vector,比较方式默认用operator<,也就是优先队列是大顶堆,队头元素最大。
定义
namespace std{
template <typename T,
typename Container = vector<T>,
typename Compare = less<typename Container::value_type> >
class priority_queue;
}
注意需要头文件:< queue >
priority_queue<int>pq1;
or
priority_queue<int,deque<int> >pq3;
自定义类型
priority_queue<int,vector<int>,greater<int> >pq2;//优先级定义为数字小的优先级大
相关函数
入队,如例:heap.push(x); 将x 接到队列的末端。
出队,如例:heap.pop(); 弹出队列的第一个元素,注意,并不会返回被弹出元素的值。
访问队首元素,如例:heap.front(),即最早被压入队列的元素。
访问队尾元素,如例:heap.back(),即最后被压入队列的元素。
判断队列空,如例:heap.empty(),当队列空时,返回true。
访问队列中的元素个数,如例:heap.size()
插入元素push()
int a[]={,,,,,,,,,};
for(int i=;i<;i++)
{
pq1.push(a[i]);
}
删除元素pop()
pq1.pop();//即删除队头元素,出队
取队头元素top()
int e = pq1.top();//将队头元素的值赋给e
大小
int size = pq1.size();
实例
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std; int main()
{
priority_queue<int>pq1; //默认是降序
int a[]={,,,,,,,,,};
for(int i=;i<;i++)
{
pq1.push(a[i]);
}
while(!pq1.empty()){
printf("%d ",pq1.top());//打印出9 8 7 6 5 5 4 3 2 1
pq1.pop();
}
printf("\n"); priority_queue<int,vector<int>,greater<int> >pq2;//可以重写成升序
int b[]={,,,,,,,,,};
for(int i=;i<;i++)
{
pq2.push(b[i]);
}
while(!pq2.empty()){
printf("%d ",pq2.top());//打印出1 2 3 4 5 5 6 7 8 9
pq2.pop();
}
printf("\n");
priority_queue<int,deque<int> >pq3;
int c[]={,,,,,,,,,};
for(int i=;i<;i++)
{
pq3.push(c[i]);
}
int size = pq3.size();
printf("%d\n",size); //输出10
while(!pq3.empty()){
printf("%d ",pq3.top());//打印出9 8 7 6 5 5 4 3 2 1
pq3.pop();
}
return ;
}