目录
priority_queue的介绍和使用
priority_queue的介绍
1、优先级队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
2、其底层类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3、优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4、底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
- empty()：检测容器是否为空
- size()：返回容器中有效元素个数
- front()：返回容器中第一个元素的引用
- push_back()：在容器尾部插入元素
- pop_back()：删除容器尾部元素
5、标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
6、需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
priority_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。
函数声明 接口说明 priority_queue()/priority_queue(first,last) 构造一个空的优先级队列 empty 检测优先级队列是否为空，是返回true，否则返回false top() 返回优先级队列中最大(最小元素)，即堆顶元素 push() 在优先级队列中插入元素 pop() 删除优先级队列中最大(最小)元素，即堆顶元素
- priority_queue的定义方式：
1、使用vector作为底层容器，内部构造大堆结构：
priority_queue<int, vector<int>, less<int>> q1;2、使用vector作为底层容器，内部构造小堆结构：
priority_queue<int, vector<int>, greater<int>> q2;3、不指定底层容器和内部需要构造的堆结构。(编译器默认大堆处理)
priority_queue<int> pq;
- 测试如下：
void test_priority_queue() { priority_queue<int> q; q.push(3); q.push(5); q.push(0); q.push(7); q.push(9); q.push(1); while (!q.empty()) { cout << q.top() << " "; // 9 7 5 3 1 0 q.pop(); } cout << endl; }：优先级队列默认大的优先级高，传的是less仿函数，底层是一个大堆。如果想要控制小的优先级高，需要传greater仿函数，底层是一个小堆。
仿函数
- 概念：
仿函数，即函数对象。一种行为类似函数的对象，调用者可以像函数一样使用该对象，其实现起来也比较简单：用户只需要实现一种新类型，在类中重载operator()即可，参数根据用户所要进行的操作选择匹配。
- 测试：
如下为内置类型比较大小关系：
//仿函数/函数对象—对象可以像调用函数一样去使用 struct less { //()运算符重载-用于比较大小 bool operator()(int x, int y) { return x < y; } };
- 自定义类型比较less：
template<class T> struct less //用于 < 的比较 { bool operator()(const T& x, const T& y)const { return x < y; } };
- 自定义类型比较greater：
template<class T> struct greater//用于 > 的比较 { bool operator()(const T& x, const T& y) const { return x > y; } };
- less和greater的测试：
//测试less less<int> LessCom; cout << LessCom(1, 2) << endl; //1 //测试greater greater<int> GreaterCom; cout << GreaterCom(1, 3) << endl; //0仿函数less、greater在<functional>里面。
：仿函数这里还可以用函数指针，只不过会比较麻烦，不建议用。
- 我们优先级队列传仿函数，传的是类型，而对于sort，传的是参数，我们就需要写成less<int>()。如果我们自己写greater仿函数等等，存储的是自定义类型，用sort传仿函数。
- 测试：
//商品 struct Goods { string _name; double _price; size_t _saleNum; //... /*bool operator<(const Goods& g) const { return _price < g._price; }*/ }; struct LessPrice { bool operator()(const Goods& g1, const Goods& g2) const { return g1._price < g2._price; } }; struct GreaterPrice { bool operator()(const Goods& g1, const Goods& g2) const { return g1._price > g2._price; } }; struct LessSaleNum { bool operator()(const Goods& g1, const Goods& g2) const { return g1._saleNum < g2._saleNum; } }; struct GreaterSaleNum { bool operator()(const Goods& g1, const Goods& g2) const { return g1._saleNum > g2._saleNum; } }; void test_functional() { vector<int> v; v.push_back(2); v.push_back(1); v.push_back(4); v.push_back(5); v.push_back(3); for (auto e : v) { cout << e << " "; } cout << endl; // less sort(v.begin(), v.end()); for (auto e : v) { cout << e << " "; } cout << endl; // greater sort(v.begin(), v.end(), greater<int>()); for (auto e : v) { cout << e << " "; } cout << endl; // 指向数组的原生指针，本身就是天然迭代器 int a[6] = { 1, 2, 5, 2, 5, 7 }; sort(a, a + 6); sort(a, a + 6, greater<int>()); Goods gds[4] = { { "苹果", 2.1, 1000}, { "香蕉", 3.0, 200}, { "橙子", 2.2,300}, { "菠萝", 1.5,50} }; sort(gds, gds + 4, LessPrice()); sort(gds, gds + 4, GreaterPrice()); sort(gds, gds + 4, LessSaleNum()); sort(gds, gds + 4, GreaterSaleNum()); }
堆的调整算法
- 堆的向上调整算法
//向上调整算法 void AdjustUp(int child) { int parent = (child - 1) / 2; while (child > 0) { //利用仿函数建大堆或小堆 if (comFunc(_con[parent], _con[child])) { //如果为真，交换 swap(_con[parent], _con[child]); //更新child和parent child = parent; parent = (child - 1) / 2; } else { //此时不需要调整，直接break break; } } }
- 堆的向下调整算法
//向下调整算法 void AdjustDown(int parent) { int child = parent * 2 + 1; while (child < _con.size()) { if (child + 1 < _con.size() && comFunc(_con[child], _con[child + 1])) { //如果为真，++child child++; } //利用仿函数建堆 if (comFunc(_con[parent], _con[child])) { //如果为真，交换 swap(_con[parent], _con[child]); //更新child和parent parent = child; child = parent * 2 + 1; } else { //此时不需要调整，直接break break; } } }：在算法库里面也有关于堆的一些函数可以直接用。
priority_queue的模拟实现
有了上文仿函数、堆调整算法基础以后，priority_queue实现起来就特别容易了。
- 实现代码：
namespace Fan { //比较方式(使内部结构为大堆) template<class T> struct less { bool operator()(const T& x, const T& y) { return x < y; } }; //比较方式(使内部结构为小堆) template<class T> struct greater { bool operator()(const T& x, const T& y) { return x > y; } }; //优先级队列的模拟实现 template<class T,class Container=vector<T>,class Compare=less<T>> class priority_queue { public: //构造函数 priority_queue(const Compare& comFunc = Compare()) :_comFunc(comFunc) {} template<class InputIterator> priority_queue(InputIterator first, InputIterator last, const Compare& comFunc = Compare()) : _comFunc(comFunc) { while (first != last) { _con.push_back(*first); ++first; } //建堆 for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--) { AdjustDown(i); } } //向上调整算法 void AdjustUp(int child) { int parent = (child - 1) / 2; while (child > 0) { if (_comFunc(_con[parent], _con[child])) { swap(_con[parent], _con[child]); child = parent; parent = (child - 1) / 2; } else { break; } } } //插入元素 void push(const T& x) { _con.push_back(x); AdjustUp(_con.size() - 1); } //向下调整算法 void AdjustDown(int parent) { size_t child = parent * 2 + 1; while (child < _con.size()) { if (child + 1 < _con.size() && _comFunc(_con[child], _con[child + 1])) { child++; } if(_comFunc(_con[parent], _con[child])) { swap(_con[parent], _con[child]); parent = child; child = parent * 2 + 1; } else { break; } } } //删除元素 void pop() { assert(!_con.empty()); swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); AdjustDown(0); } //取队顶数据 const T& top() { return _con[0]; } //获取size有效数据个数 size_t size() { return _con.size(); } //判空 bool empty() { return _con.empty(); } private: Container _con; Compare _comFunc; }; }
- 我们默认使用less仿函数，下面我们测试一下：
void test_priority_queue() { Fan::priority_queue<int> pq; pq.push(8); pq.push(3); pq.push(6); pq.push(2); pq.push(7); cout << pq.size() << endl; //5 while (!pq.empty()) { cout << pq.top() << " "; // 8 7 6 3 2 pq.pop(); } }
- 下面我们把仿函数改成greater：
文章评论