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
