推荐阅读：C++ priority_queue 与 lambda的结合使用
#include <queue> 头文件
priority_queue<Type, Container, Functional>
默认是大顶堆
greater<>成为小顶堆priority_queue<int, vector<int>, greater<int> > q;
加入 q.push();
弹出 q.pop();
队头 q.top();
对于自定义类型，则必须自己重载 operator< 或者自己写仿函数
这里得仿函数做的是判断当前值得大小往后放，因此，greater<>，大的元素往后放，就是小顶堆。
struct Node{ int x, y; Node(int a= 0, int b= 0 ): x(a), y(b) {} }; bool operator<( Node a, Node b ){ if( a.x== b.x ) return a.y> b.y;//小顶堆 return a.x> b.x; } 也可以使用函数对象实现：
#include <iostream> #include <queue> using namespace std; struct Node{ int x, y; Node( int a= 0, int b= 0 ): x(a), y(b) {} }; struct cmp{ bool operator() ( Node a, Node b ){ if( a.x== b.x ) return a.y> b.y; return a.x> b.x; }// 小顶堆 }; int main(){ priority_queue<Node, vector<Node>, cmp> q; for( int i= 0; i< 10; ++i ) q.push( Node( rand(), rand() ) ); while( !q.empty() ){ cout << q.top().x << ' ' << q.top().y << endl; q.pop(); } getchar(); return 0; }
例题：
1、美团2016 字符编码
请设计一个算法，给一个字符串进行二进制编码，使得编码后字符串的长度最短。 输入描述: 每组数据一行，为待编码的字符串。保证字符串长度小于等于1000。 输出描述: 一行输出最短的编码后长度。 输入例子1: MT-TECH-TEAM 输出例子1: 33
自己的思路：
自己独立更改了很多次，核心的方法是哈夫曼编码。首先使用一个map统计所有字符出现的次数，放入一个小顶堆，堆的值按照次数排序。每次弹出两个最小的两个，构建成一个节点后再加入堆中。当堆为空时，说明所有节点都处理完成。
更改很多次的原因是，怎么迎合题目输出的要求。举例：一个节点的次数是2，当他和其他节点构成一个新的节点时，编码长度的改变是：这个节点对应的两个相同字符都加一。
因此，堆中存储的数据更改为一个结构体{sum,node}，sum表示这个节点目前的编码长度统计（默认带有前支），node代表当前节点的权值；
每次构建一个新节点时，新节点的sum=两个节点的sum之和，同时要加上两个节点的权值之和（因为有产生一个向上的分支，这个权值代表的是当前这个综合节点的字符数量），新的节点探入{新的sum，权值之和}
特殊情况：当队列为空时，只有一个节点了，这个时候的sum只是两个sum的和，不能再加上两个节点的权值和（根节点没有向上的分支）
代码如下：
#include<iostream> #include<vector> #include<string> #include<queue> #include<map> using namespace std; struct code{ int sum; int node; }; bool operator<(code a,code b){ if(a.node==b.node) return a.sum>b.sum; return a.node>b.node; } int main() { //哈夫曼编码 string input; while(cin>>input) { map<char,int> sta; priority_queue<code,vector<code>> q; for(auto s:input) { sta[s]++; } for(auto s:sta) q.push({s.second,s.second}); int n=q.size()-1; int sum=0; if(n==0) sum=1; while(n!=0&&!q.empty()) { code left=q.top(); q.pop(); code right=q.top(); q.pop(); int temp=left.sum+right.sum+left.node+right.node; if(!q.empty()) q.push({temp,left.node+right.node}); if(q.empty()) sum=temp-left.node-right.node;//到根节点，将向上分支多加的减掉 } cout<<sum<<endl; } //system("pause"); return 0; }
2 378. Kth Smallest Element in a Sorted Matrix
http://blog.csdn.net/m0_37693059/article/details/77772048
使用了
priority_queue<pair<int, pair<int, int>>> myQueue;make_pair ,emplace,lambda表达式等
greater<pair<int,int>> 默认比较第一个值
