对于priority_queue，头文件包含在queue.h中，用来实现堆排序，默认是小根堆（小的在前）
函数声明：
template <class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class priority_queue;
对于sort(),函数声明：
template <class RandomAccessIterator>
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last );
template <class RandomAccessIterator, class Compare>
void stable_sort ( RandomAccessIterator first, RandomAccessIterator last,
Compare comp );
关于有关自定义排序的Compare comp，我们来看对它的描述：
comp Binary function that accepts two elements in the range as
arguments, and returns a value convertible to bool. The value returned
indicates whether the element passed as first argument is considered
to go before the second in the specific strict weak ordering it
defines. The function shall not modify any of its arguments.This can
either be a function pointer or a function object.
很明确的表示了comp是一个函数指针或函数对象
sort自定义有如下两种方法：
- 可以自定义一个bool型函数，里面的大小规则要是严格弱序的，然后把这个函数名作为参数传给sort；
- 还可以写一个struct或者class，注意要在这个结构体or类中重载调用运算符。然后利用这个结构体or类去实例化一个对象，也就是所谓的函数对象（当成）。把这个函数对象传递给sort也可以完成自定义排序。
可参考具体见：【C++&Leetcode】浅析map与sort的自定义排序
注意
return中的 “>” 和 “<” 符号
优先队列中的排序大小与结构体里重载的符号相反
sort()函数中的排序大小与结构体里重载的符号一致
假设node是一个class类以下方式可以实现重载
struct cmp
{
bool operator()(const node &a, const node &b){
return a.val > b.val; // 大于表示小的在前，小根堆
// 对于sort则相反，大于表示大的在前，降序
}
};
priority_queue<node, vector<node>, cmp> pq;
这里插入一下，对于set重载，这个const 是必不可少的，少了其中一个都会报错：
struct cmp {
//下面形参的const 和 形参之后的 const都不可缺少，不然不能使用set成员函数
bool operator () (const int& a, const int& b) const {
return a > b;
}
//以下写法均不可行
//bool operator () (int& a, int& b) {}
//bool operator () (int& a, int& b) const {}
//bool operator () (const int& a, const int& b) {}
};
set<int, cmp> st;
// 上面的重载相当于 set<int,greater<int>> st;
class Solution {
public:
int thirdMax(vector<int>& nums) {
for (auto s : nums) st.insert(s);
int i = 0;
int res = INT_MIN;
for (auto s : st) {
if (s >= res) res = s;
i++;
if (i == 3) {
res = s;
break;
}
}
return res;
}
};
可用如下方法验证：
#include "HuffmanTree.hpp"
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
struct Comp {
bool operator() (const int & a, const int& b) const{
return a > b;
}
};
int main() {
vector<int> a = { 3, 1, 7, 5 };
vector<int> b = a;
sort(a.begin(), a.end(), Comp());
for (int i = 0; i < 4; i++) cout << a[i] << ' ';
cout << endl;
priority_queue<int, vector<int>, Comp> q;
for (int i = 0; i < 4; i++) q.push(b[i]);
for (int i = 0; i < 4; i++) cout << q.top() << ' ', q.pop();
return 0;
}
输出结果：
可以看到，sort()里是降序排列，而优先队列是小根堆（和默认的less一样）
sort重载是否加()的问题：
注意：这里的重载符号是写在结构体里面的，所以对于sort来说，重载时要明确函数指针 or 函数对象 ，Comp在这里是一个struct类型，对其取括号，就是取得里面的函数对象（类型的构造函数）
故要写成
struct Comp {
bool operator() (const int & a, const int& b) const{
return a > b;
}
};
int main() {
vector<int> a = { 3, 1, 7, 5 };
sort(a.begin(), a.end(), Comp());
return 0;
}
只要明确了sort重载时，第三个参数要写入的是一个对象，而不是类型，就可以了解不同重载的写法下，加不加()，如下写法不用加括号:
struct Comp {
bool operator() (const int & a, const int& b) const{
return a > b;
}
}Comp;
int main() {
vector<int> a = { 3, 1, 7, 5 };
sort(a.begin(), a.end(), Comp);
return 0;
}
（由类构造对象的过程称为创建类的实例
类只是一个模板（Template），编译后不占用内存空间，所以在定义类时不能对成员变量进行初始化，因为没有地方存储数据。只有在创建对象以后才会给成员变量分配内存，这个时候就可以赋值了）
原因是，在struct的时候用Comp这个类型实例化了一个同名的对象Comp，所以在sort里面的Comp，实际上已经是一个对象了，故不需要加()，来调用一个类型的函数对象，以下写法也是正确的：
bool Comp (const int& a, const int& b) {
return a > b;
}
int main() {
vector<int> a = { 3, 1, 7, 5 };
sort(a.begin(), a.end(), Comp);
return 0;
}
· 函数名和指针的关系 函数名也是一种指针，因为函数名是函数的入口地址，所以函数的名字就可以被赋值一个对应的函数指针了，我们我可以通过函数指针来调用这个函数。
这里的Comp可认为是一个函数指针。
priority_queue
对于优先队列的重载就不需要是对象，而第三个参数要是一个类型
题目开始的例子：可以很好的说明问题，queue重载的就是一个类型Comp，而sort重载时需要对象，故写Comp()—对象是Comp的构造函数。
#include "HuffmanTree.hpp"
#include <iostream>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
struct Comp {
bool operator() (const int & a, const int& b) const{
return a > b;
}
};
int main() {
vector<int> a = { 3, 1, 7, 5 };
vector<int> b = a;
sort(a.begin(), a.end(), Comp());
for (int i = 0; i < 4; i++) cout << a[i] << ' ';
cout << endl;
priority_queue<int, vector<int>, Comp> q;
for (int i = 0; i < 4; i++) q.push(b[i]);
for (int i = 0; i < 4; i++) cout << q.top() << ' ', q.pop();
return 0;
}
假设Node是一个类模板：
template<class W>
struct HuffmanTreeNode {
typedef HuffmanTreeNode<W> Node;
Node* _left;
Node* _right;
Node* _parent;
W _weight;
HuffmanTreeNode(const W& w = w())
: _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _weight(w)
{}
};
则用优先队列，由类内部的成员_weight创建小根堆的重载方式如下：
template<class W>
struct comp {
typedef HuffmanTreeNode<W> Node;
bool operator() (const Node* comp_1, const Node* comp_2) {
return comp_1->_weight > comp_2->_weight; // 大于创建小根堆，小的在堆头，实现按结构体中的成员_weight的值来排序
}
};
int main() {
priority_queue<Node*, vector<Node*>, comp<W>> q; //创建方法
}
上面如果直接使用
priority_queue<Node*, vector<Node*>, greater<Node*>> q;
则是按找Node的地址大小排序，显然是不被需要的。