1.priority_queue
priority_queue是一个优先队列,下面是他的声明,我们平时可以直接使用下面的方式声明一个优先队列。
priority_queue<int> pq
优先队列内部是一个heap的实现,也就是说默认push到priority_queue中的数据,当我们pop出来的时候,默认是优先级最高的,(数字大的优先级高,数字小的优先级低),这个数据结构默认使用vector作为容器,cmp函数默认使用less作为比较函数。
下面的是一个完整的priority_queue的声明
std::priority_queue template <class T, class Container = vector<T>, class Compare = less < typename Container::value_type> > class priority_queue;
priority_queue<Type, Container, Functional>
其中Type 为数据类型, Container 为保存数据的容器,Functional 为元素比较方式。Container 必须是用数组实现的容器,比如 vector, deque 但不能用 list。STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果把后面俩个参数缺省的话,优先队列就是大顶堆,队头元素最大。
我们使用的时候和平常queue的方式没有什么太大的却别,最大的区别在于这个cmp应该如何自定义。我们知道cmp是一个函数指针,所以我们可以有两种方式重载cmp函数。
struct cmp { bool operator () (int &a, int &b) { return a > b ; // 从小到大排序,值 小的 优先级别高 } }; priority_queue<int,vector<int>,cmp> q;
方式1:
struct Time { int h; int m; int s; }; class CompareTime { public: bool operator()(Time& t1, Time& t2) // Returns true if t1 is earlier than t2 { if (t1.h < t2.h) return true; if (t1.h == t2.h && t1.m < t2.m) return true; if (t1.h == t2.h && t1.m == t2.m && t1.s < t2.s) return true; return false; } }
这里我们必须保证重载的()函数返回值是bool,上面的重载函数核心就是当t1<t2时候,返回tree,所以得到的也就是从大到小的排列,也是这个数据结构默认的,如果我们想重新实现这个数据结构,改为从小到大排列,那么可以使用下面的方式
方式2:
class CompareTime { public: bool operator()(Time& t1, Time& t2) // t2 has highest prio than t1 if t2 is earlier than t1 { if (t1.h > t2.h) return true; if (t2.h == t1.h && t2.m < t1.m) return true; if (t2.h == t1.h && t2.m == t1.m && t2.s < t1.s) return true; return false; } };
保证第一个大于第二个返回true即可。
上面我们看到在一个class类里面重载()函数,我们也可以在要使用的类里面,使用struct{}方式。
class Solution { public: ..... private: struct cmp { bool operator()(ListNode* node1, ListNode* node2) { return node1->val > node2->val; } }; };
在C/C++中,我们可以等同class与struct相似。
2.heap
heap 主要分为push_heap、pop_heap、sort_heap、reverse四个函数,我们使用这四个函数使得vector中数据按照heap来排列。
make_heap的两种形式:
template <class RandomAccessIterator> void make_heap (RandomAccessIterator first, RandomAccessIterator last); template <class RandomAccessIterator, class Compare> void make_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp );
同样有一个comp函数可以指定以排列顺序,所以priority_queue是基于heap的方式来实现的。
示例代码:
#include <iostream> #include <algorithm> #include <vector> using namespace std; class priority_queue { private: vector<int> data; public: void push( int t ){ data.push_back(t); push_heap( data.begin(), data.end()); } void pop(){ pop_heap( data.begin(), data.end() ); data.pop_back(); } int top() { return data.front(); } int size() { return data.size(); } bool empty() { return data.empty(); } }; int main() { priority_queue test; test.push( 3 ); test.push( 5 ); test.push( 2 ); test.push( 4 ); while( !test.empty() ){ cout << test.top() << endl; test.pop(); } return 0; }
参考:
[1] http://comsci.liu.edu/~jrodriguez/cs631sp08/c++priorityqueue.html
[2] http://www.cplusplus.com/reference/queue/priority_queue/
[3] http://stackoverflow.com/questions/23529815/how-to-use-stdmake-heap
[4] http://www.cppblog.com/mzty/archive/2005/12/15/1770.html