C++ priority_queue用法
以上大多摘自c++官网优先队列是一种容器适配器。它的第一个元素总是包含元素的最大值。优先队列类似于堆,可以随时插入新的元素,只有堆中最大的元素可以被访问(优先队列队首元素)。优先队列属于容器适配器,即优先队列本身也封装了容器,并提供了一些接口来访问成员。优先队列封装的容器必须支持随机访问,并且支持empty(),size(),front(),push_back(),pop_back()...
·
以上大多摘自c++官网
优先队列是一种容器适配器。它的第一个元素总是包含元素的最大值。
优先队列类似于堆,可以随时插入新的元素,只有堆中最大的元素可以被访问(优先队列队首元素)。
优先队列属于容器适配器,即优先队列本身也封装了容器,并提供了一些接口来访问成员。优先队列封装的容器必须支持随机访问,并且支持empty(),size(),front(),push_back(),pop_back()成员函数。
支持随机访问是英文这样可以维护堆数据结构。优先队列会在必要的时候自动调用make_heap,push_heap或pop_heap来维护堆数据结构。
优先队列的定义:
template <class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class priority_queue;
T:优先队列内元素类型。
Container:优先队列封装的容器类型。
Compare:二元比较对象,比较两个T对象的大小。当比较两个对象a、b的时候,如果a在b的前面则返回true。优先队列用这个比较对象来维护堆的性质。(pop出来的元素是最后一个元素)
主要成员函数:
empty():判断优先队列是否为空
size():判断优先队列大小
top():返回优先队列的top元素,top元素是比较后更大的那个元素。
push():插入一个对象到优先队列中
pop():返回队首(top)元素
emplace():以形参为构造函数的参数,构造新的对象插入到优先队列中。
top成员函数返回的是排在最后的元素。如果compare比较cmp(a,b)是a<b返回true,则更小的排在前面。top返回的是最大元素(大顶堆)
// priority_queue::top
#include <iostream> // std::cout
#include <queue> // std::priority_queue
int main ()
{
std::priority_queue<int> mypq;
mypq.push(10);
mypq.push(20);
mypq.push(15);
std::cout << "mypq.top() is now " << mypq.top() << '\n';
return 0;
}
stdout:mypq.top() is now 20
)
更多推荐
已为社区贡献1条内容
所有评论(0)