介绍
priority queue优先级队列,它的接口和queue非常相似,有入队push(),获取第一个元素top(),pop删除第一个元素。这里的第一个元素并不是第一个放入的元素,而是"优先级最高"的元素。
priority queue内的元素已经根据其值进行了排序。当然你可以通过参数指定一个排序准则,默认的排序是升序排列。所谓的第一个元素就是当前"数值最大的元素"(默认的vector,第一个"最大值"元素保存在最后,因为vector尾删效率高)。如果同时存在多个数值最大的元素,我们无法确定哪一个在前哪一个在后。
其内部数据结构为:大根堆
不能使用list作为其容器
priority queue也是定义在头文件中
namespace std {
template < typename T,
typename Container=vector<Type>,
typename Compare=less<typename Container::value_type> >
class priority_queue;
}
第一个参数T是元素类型,第二个参数为内部存放元素的容器,默认为vector,第三个参数是排序规则,默认是升序(less)。下面定义一个int的priority queue。
priority_queue<int> pq;//定义一个int的优先级队列
实际上priority queue优先级队列只是简单的把各项操作转为内部容器对应的函数调用。你当然可以使用支持随机迭代器(需要排序),front(),push_back(),pop_back()等操作的标准容器作为内部容器。例如可以使用deque作为内部容器。
priority_queue<int,deque<int>> pq2;//创建一个int的优先级队列,并使用deque作为存放数据的容器
当然你也可以定义自己的排序准则,例如下面使用一个降序排序规则。
priority_queue<int,vector<int>,greater<int>> pq3;//创建一个int的优先级,使用vector存放数据,并按降序排列
在上面的priority queue pq3中,"下一个元素"始终是元素值最小的(降序最后一个元素,值最小)。
定义及初始化
priority queue的初始化方式比较丰富,具体如下:
//优先级队列
#include <queue>
#include <iostream>
using namespace std;
int main()
{
priority_queue <int> q1;//创建一个保存int的空优先级队列
if (q1.empty())
cout << "q1是空的,它的数据个数为:" << q1.size() << endl;
//创建一个保存int,且用deque保存内部数据的优先级队列(默认为升序)
priority_queue <int, deque <int> > q2;
q2.push(5); //入队
q2.push(15);//入队
q2.push(10);//入队
cout << "q2的数据:";
while (!q2.empty())//只要q2不为空,循环继续
{
cout << q2.top() << " "; //输出第一个元素的值(最大)
q2.pop(); //删除第一个元素
}
cout << endl;
//创建保存int,用vector保存内部数据且降序的优先级队列
priority_queue <int, vector<int>, greater<int> > q3;
q3.push(2); //入队
q3.push(1);//入队
q3.push(3);//入队
cout << "q3的数据:";
while (!q3.empty())
{
cout << q3.top() << " ";//输出第一个元素的值(最小)
q3.pop(); //删除第一个元素
}
cout << endl;
q1.push(100);
q1.push(200);
//利用q1创建一个新的优先级队列q4
priority_queue <int> q4(q1);
cout << "q4 的数据:";
while (!q4.empty())
{
cout << q4.top() << " ";
q4.pop();
}
cout << endl;
// 利用迭代器创建优先级队列
vector <int> v5{10,30,20,40};
priority_queue <int> q5(v5.begin(), v5.end());
cout << "q5的数据:";
while (!q5.empty())
{
cout << q5.top() << " ";
q5.pop();
}
cout << endl;
return 0;
}
常用操作
priority queue优先级队列的操作比较简单,只要几个简单的成员函数。
empty成员函数
判断优先级队列是否为空。是返回true,不是返回false。
pop成员函数
把第一个元素从队列删除。
push成员函数
往优先级队列中插入一个数据。
size成员函数
返回优先级队列数据个数。
top成员函数
返回第一个元素的引用。
int main()
{
priority_queue<int> q; //创建一个空优先级队列
if (q.empty())
cout << "q是一个空队" << endl;
q.push(3);
q.push(2);
q.push(5);
q.push(4);
q.push(1);
cout << "插入5个数据之后,当前的数据个数为" << q.size() << endl;
cout << "依次出队的数据为:";
while (!q.empty())//只要q1不为空,循环继续
{
cout << q.top() << " ";
q.pop();
}
return 0;
}
深入priority queue
priority queue优先级队列内部是使用STL的堆排序heap算法
下面是queue文件部分源码:
template <class _Ty, class _Container = vector<_Ty>,
class _Pr = less<typename _Container::value_type>>
class priority_queue
{
protected:
_Container c{};//容器
_Pr comp{}; //比较函数对象
public:
template <class _Alloc, enable_if_t<uses_allocator_v<_Container,_Alloc>, int>= 0>
priority_queue(const _Pr& _Pred, const _Container& _Cont, const _Alloc& _Al) :
c(_Cont, _Al), comp(_Pred)//构造函数
{
make_heap(c.begin(), c.end(), comp);//变成堆(默认为大根堆)
}
void push(const value_type& _Val) {
c.push_back(_Val);
push_heap(c.begin(), c.end(), comp);//往堆增加一个元素
}
void pop() {
pop_heap(c.begin(), c.end(), comp);//从堆中删除一个元素
c.pop_back();
}
}
通过priority_queue的实现源码可以看到,其内部使用heap的函数。
