STL中的优先队列
首先这是一个队列,只允许在底端加入元素,并从顶端取出元素,除此之外别无其他存取元素的途径。
priority_queue带有权值观念,元素并非按照被推入的次序排列,而是自动按照元素的权值排列。权值最高者,排在最前面。缺省情况下priority_queue利用一个MAX-HEAPIFY完成,以vector表现的完全二叉树(complete binary tree)。
queue以底部容器vector完成其所有工作,具有这种“修改某物接口,形成另一种风貌”之性质这,称为配接器(adapter)。STL priority_queue被归类为container adapter。
1 2 3 |
_Tp: Type of the elements. _Sequence: Type of the underlying container object used to store and access the elements. _Compar: Comparison class: A class such that the expression comp(a,b), where comp is an object of this class and a and b are elements of the container, returns true if a is to be placed earlier than b in a strict weak ordering operation. This can either be a class implementing a function call operator or a pointer to a function. This defaults to less<T>, which returns the same as applying the less-than operator (a<b). 可以自定义一个比较类,Compare |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
template <class _Tp, class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(vector<_Tp>), class _Compar __STL_DEPENDENT_DEFAULT_TMPL(less<typename _Sequence::value_type>) >//小于比较符 class priority_queue { // requirements: __STL_CLASS_REQUIRES(_Tp, _Assignable); __STL_CLASS_REQUIRES(_Sequence, _Sequence); __STL_CLASS_REQUIRES(_Sequence, _RandomAccessContainer); typedef typename _Sequence::value_type _Sequence_value_type; __STL_CLASS_REQUIRES_SAME_TYPE(_Tp, _Sequence_value_type); __STL_CLASS_BINARY_FUNCTION_CHECK(_Compare, bool, _Tp, _Tp); public: typedef typename _Sequence::value_type value_type; typedef typename _Sequence::size_type size_type; typedef _Sequence container_type; typedef typename _Sequence::reference reference; typedef typename _Sequence::const_reference const_reference; protected: _Sequence c; //底层容器 _Compare comp;//元素大小比较标准 public: priority_queue() : c() {} explicit priority_queue(const _Compare& __x) : c(), comp(__x) {}//显示构造函数 priority_queue(const _Compare& __x, const _Sequence& __s) : c(__s), comp(__x) { make_heap(c.begin(), c.end(), comp); } //make_heap(),push_heap(),pop_heap()都是泛型算法 #ifdef __STL_MEMBER_TEMPLATES //这是一个拷贝构造函数,传递入vector的开始迭代器位置和结束迭代器位置,进行建堆操作 template <class _InputIterator> priority_queue(_InputIterator __first, _InputIterator __last) : c(__first, __last) { make_heap(c.begin(), c.end(), comp); } //同样的拷贝构造函数,指定比较标准 template <class _InputIterator> priority_queue(_InputIterator __first, _InputIterator __last, const _Compare& __x) : c(__first, __last), comp(__x) { make_heap(c.begin(), c.end(), comp); } //插入一个vector,然后进行建堆操作 template <class _InputIterator> priority_queue(_InputIterator __first, _InputIterator __last, const _Compare& __x, const _Sequence& __s) : c(__s), comp(__x) { c.insert(c.end(), __first, __last); make_heap(c.begin(), c.end(), comp); } #else /* __STL_MEMBER_TEMPLATES */ priority_queue(const value_type* __first, const value_type* __last) : c(__first, __last) { make_heap(c.begin(), c.end(), comp); } priority_queue(const value_type* __first, const value_type* __last, const _Compare& __x) : c(__first, __last), comp(__x) { make_heap(c.begin(), c.end(), comp); } priority_queue(const value_type* __first, const value_type* __last, const _Compare& __x, const _Sequence& __c) : c(__c), comp(__x) { c.insert(c.end(), __first, __last); make_heap(c.begin(), c.end(), comp); } #endif /* __STL_MEMBER_TEMPLATES */ bool empty() const { return c.empty(); } //注意到这里size()函数返回的是size_type类型,不然会报错 size_type size() const { return c.size(); } const_reference top() const { return c.front(); } void push(const value_type& __x) { __STL_TRY { //push_heap是泛型算法,先利用底层容器的push_back()将新元素推入末端,再重排heap,cpp primer p1195 c.push_back(__x); push_heap(c.begin(), c.end(), comp); } __STL_UNWIND(c.clear()); } void pop() { __STL_TRY { //pop_heap是泛型算法,先从Heap中取出一个元素,它并不是真正将元素弹出,而是重排heap,然后再以底层容器的pop_back()取得被弹出的元素 pop_heap(c.begin(), c.end(), comp); c.pop_back(); } __STL_UNWIND(c.clear()); } }; |
priority_queue没有迭代器
priority_queue不提供遍历功能,也不提供迭代器。
Container 必须是用数组实现的容器,比如 vector,deque 但不能用 list。STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果把后面俩个
参数缺省的话,优先队列就是大顶堆,队头元素最大。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
#include <queue> #include <iostream> using namespace std; int _tmain(int argc, _TCHAR* argv[]){ int ia[9]={0,1,2,3,4,8,9,3,5}; priority_queue<int>ipq(ia,ia+9); cout<<"size="<<ipq.size()<<endl; for(int i=0;i<ipq.size();++i){ cout<<ipq.top()<<' '; } cout<<endl; while(!ipq.empty()){ cout<<ipq.top()<<' '; ipq.pop(); } cout<<endl; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <queue> #include <iostream> using namespace std; struct Node{ int x, y; Node( int a= 0, int b= 0 ): x(a), y(b) {} }; //对于自定义类型,则必须自己重载 operator< 或者自己写仿函数 bool operator<( Node a, Node b ){ if( a.x== b.x ) return a.y> b.y; return a.x> b.x; } int _tmain(int argc, _TCHAR* argv[]){ priority_queue<Node> q; //vector<Node> ia; for( int i= 0; i< 10; ++i ) q.push( Node( 10-i, 10-i-1 ) ); while( !q.empty() ){ cout << q.top().x << ' ' << q.top().y << endl; q.pop(); } return 0; } |
VS中的heap
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
//alogorithm.h中的源码 template<class _RanIt> inline void make_heap(_RanIt _First, _RanIt _Last) { // make [_First, _Last) into a heap, using operator< _DEBUG_RANGE(_First, _Last); if (1 < _Last - _First) _Make_heap(_Unchecked(_First), _Unchecked(_Last), _Dist_type(_First), _Val_type(_First)); } template<class _RanIt> inline void make_heap(_RanIt _First, _RanIt _Last) { // make [_First, _Last) into a heap, using operator< _DEBUG_RANGE(_First, _Last); if (1 < _Last - _First) _Make_heap(_Unchecked(_First), _Unchecked(_Last), _Dist_type(_First), _Val_type(_First)); } //这里是建堆的程序,因为建最大堆,自底向上 template<class _RanIt, class _Diff, class _Ty> inline void _Make_heap(_RanIt _First, _RanIt _Last, _Diff *, _Ty *) { // make nontrivial [_First, _Last) into a heap, using operator< _Diff _Bottom = _Last - _First; for (_Diff _Hole = _Bottom / 2; 0 < _Hole; ) { // reheap top half, bottom to top --_Hole; _Ty _Val = _Move(*(_First + _Hole)); _Adjust_heap(_First, _Hole, _Bottom, _Move(_Val)); } } // TEMPLATE FUNCTION pop_heap WITH PRED template<class _RanIt, class _Diff, class _Ty, class _Pr> inline void _Adjust_heap(_RanIt _First, _Diff _Hole, _Diff _Bottom, _Ty && _Val, _Pr _Pred) { // percolate _Hole to _Bottom, then push _Val, using _Pred _Diff _Top = _Hole; _Diff _Idx = 2 * _Hole + 2; for (; _Idx < _Bottom; _Idx = 2 * _Idx + 2) { // move _Hole down to larger child if (_DEBUG_LT_PRED(_Pred, *(_First + _Idx), *(_First + (_Idx - 1)))) --_Idx; *(_First + _Hole) = _Move(*(_First + _Idx)); _Hole = _Idx; } if (_Idx == _Bottom) { // only child at bottom, move _Hole down to it *(_First + _Hole) = _Move(*(_First + (_Bottom - 1))); _Hole = _Bottom - 1; } _Push_heap(_First, _Hole, _Top, _Move(_Val), _Pred); } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include "stdafx.h" #include <stdlib.h> #include <vector> #include <algorithm> #include "iostream" using namespace std; int _tmain(int argc, _TCHAR* argv[]){ int ia[9]={0,1,2,3,4,8,9,3,5}; vector<int> ivec(ia,ia+9); make_heap(ivec.begin(),ivec.end()); for(int i=0;i<ivec.size();++i){ cout<<ivec[i]<<' '; } cout<<endl; ivec.push_back(7); push_heap(ivec.begin(),ivec.end()); for(int i=0;i<ivec.size();++i){ cout<<ivec[i]<<' '; } cout<<endl; pop_heap(ivec.begin(),ivec.end()); cout<<ivec.back()<<endl; //return but no remove ivec.pop_back();//remove for(int i=0;i<ivec.size();++i){ cout<<ivec[i]<<' '; } cout<<endl; sort_heap(ivec.begin(),ivec.end()); for(int i=0;i<ivec.size();++i){ cout<<ivec[i]<<' '; } cout<<endl; return 0; } |
参考资料:
1)http://blog.csdn.net/rushkid02/article/details/7687125
2)侯捷 《STL源码剖析》