STL —— priority_queue容器用法简介
priority_queue介绍
- 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。(默认大堆)
- 此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)。
- 优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出,其称为优先队列的顶部。
- 底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问,并支持以下操作: empty():检测容器是否为空 size():返回容器中有效元素个数 front():返回容器中第一个元素的引用 push_back():在容器尾部插入元素 pop_back():删除容器尾部元素
- 标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定priority_queue类实例化指定容器类,则使用vector。
使用
优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法将vector中元素构造成堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue。
-
priority_queue()/priority_queue(first,last) 构造一个空的优先级队列 empty( ) 检测优先级队列是否为空,是返回true,否则返回false top( ) 返回优先级队列中最大(最小元素),即堆顶元素 push(x) 在优先级队列中插入元素x pop() 删除优先级队列中最大(最小)元素,即堆顶元素
模拟实现
#include <vector> #include <algorithm> #include <iostream> namespace mypri { //仿函数 函数对象 template<class T> struct less { bool operator()(const T& x1, const T& x2){ return x1 > x2;} }; template<class T> struct greater { bool operator()(const T& x1, const T& x2){ return x1 < x2;} }; //默认大堆 template<class T, class Container = std::vector<T>, class Compare = less<T> > class priority_queue { public: void Adiustup(int child) { //up Compare com;//实例化一个对象 当伪函数使用 int partent = (child -1) / 2; while (child > 0) { if (com(_con[partent], _con[child])) { //调整后更新位置 std::swap(_con[partent], _con[child]); child = partent; partent = (child-1) / 2; }else { break; } } } void Adjustdown(int root) { //down Compare com; int partent = root; int child = 2 * partent + 1; while (child < _con.size()) { if (child + 1 < _con.size() && _con[child] < _con[child+1]) { child++; } if (com(_con[partent], _con[child])) { swap(_con[child], _con[partent]); partent = child; child = partent * 2 + 1; }else { break; } } } void push(const T& x) { _con.pushback(x); Adjustup(_con,size() - 1); } void pop() { swap(_con[0], _con[_con.size()-1]); _con.pop_back(); Adjustdown(0); } T& top() { return _con[0]; } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } private: Container _con; }; void test() { priority_queue<int, std::vector<int>, greater<int> > pro; pro.push(1); pro.push(1); pro.push(7); pro.push(4); while (!pro.empty()) { std::cout << pro.top() << " "; pro.pop(); } std::cout << std::endl; } }
下一篇:
[栈和队列]前 K 个高频元素