## priority_queue
包含头文件 ``
定义：priority_queue var;
访问：与队列不同，优先队列只能通过 top() 访问队首元素
常见 API：
1. q.push(x); 入队
2. q.pop(); 队首元素出队
3. q.top(); 获取队首元素
4. q.empty(); 检查是否为空
5. q.size(); 队列中元素个数

## 优先级设置
```cpp
priority_queue;
//Type 是数据类型，Container 为保存数据的容器，Functional 为元素比较方式

priority_queue, less> q1;
priority_queue q2;
// 两者等价
// 默认大顶堆，使用 vector 容器，从大到小队列

priority_queue, greater> q3;
// 小顶堆，从小到大排列
```

## 算子
`不需要使用 () 调用`
当数据类型为自定义类或结构体时，需要重载相应操作符。定义排序规则方式：

### 重载 operater< 或 operator>
此处有一个非常难搞的问题

- 一个是重载哪种符号
- 一个是比较时用大于还是小于号
- 引用的时候是用 less 还是 greater

有一个配套
```cpp
// 小顶堆
bool operator<(const Edge& rhs) const // 类内定义，只需要一个参数
{
return cost>rhs.cost;
}

priority_queue,less> priQue;
priority_queue priQue; //等价

// 大顶堆
bool operator<(const Edge& rhs) const // 类内定义，只需要一个参数
{
return cost }
priority_queue,less> priQue;
priority_queue priQue; //等价
```
为方便只使用前面两种，都可以直接缺省使用

- 无论什么堆都重载 <
- 大堆 <，小堆 >
- 不缺省都用 less

### 重写仿函数 cmp，声明比较类 cmp
return 中符号，与类内重载 < 相同

- < 是大顶堆
- > 是小顶堆

```cpp
// 力扣 1584
struct Edge
{
public:
int start;
int end;
int cost;
Edge(int s, int e, int c): start(s), end(e), cost(c) {}

// overloaded 'operator<' must be a binary operator (has 3 parameters)
//bool operator>(const Edge& rhs) const // 类内定义，只需要一个参数
//{
// return cost>rhs.cost;
//}
};

struct cmp
{
bool operator()(Edge a, Edge b)
{
return a.cost > b.cost; // 是大于
}
};

//priority_queue,greater> priQue;
priority_queue,cmp> priQue;
priQue.emplace(0,0,0);
priQue.emplace(2,2,2);
priQue.emplace(1,1,1);

while(priQue.size())
{
cout< cout<<" ";
priQue.pop();
}
```

# sort 函数
默认升序排列，即从小到大。
## 自定义排序方式
### lambda 函数
```cpp
struct Edge
{
public:
int start;
int end;
int cost;
Edge(int s, int e, int c): start(s), end(e), cost(c) {}
};

sort(vec.begin(), vec.end(), [&](const Edge& lsh, const Edge& rhs){
return lsh.cost < rhs.cost; // 升序 从小到大
// return lsh.cost });
```

### 自定义比较函数
- 自定义比较函数要能够在 sort 引用的范围内，因此可以`声明为静态函数`
- sort `引用时不需要 ()`

```cpp
struct Edge
{
public:
int start;
int end;
int cost;
Edge(int s, int e, int c): start(s), end(e), cost(c) {}
};

class Solution
{
public:
static bool cmp(Edge& lhs, Edge& rhs)
{
return lhs.cost < rhs.cost; // 升序
}

void test(vector& nums, int target)
{
vector vec;
vec.emplace_back(0, 0, 0);
vec.emplace_back(2, 2, 2);
vec.emplace_back(1, 1, 1);

sort(vec.begin(), vec.end(), cmp);
}
};
```

### 重载 < 运算符
```cpp
struct Edge
{
public:
int start;
int end;
int cost;
Edge(int s, int e, int c): start(s), end(e), cost(c) {}

bool operator<(const Edge& rhs)
{
return cost < rhs.cost; // 升序
}
};

sort(vec.begin(), vec.end());
```

### 声明比较类
需要使用 (）
```cpp
struct cmp
{
bool operator()(Edge& lhs, Edge& rhs)
{
return lhs.cost < rhs.cost; // 升序
}
};

sort(vec.begin(), vec.end(), cmp());
```

# 总结

1. 优先队列有 3 种方法，sort 有 4 种
2. 默认排序方式
1. 优先队列反直觉，< 是大，> 是小
2. sort 正好相反
3. 只有 sort 函数在调用比较类时需要使用 ()