优先级队列简介
优先级队列priority_queue，可以在队列中自定义数据的优先级, 让优先级高的排在队列前面优先出队。它具有队列的所有特性，包括队列的基本操作，只是在这基础上添加了内部的一个排序，它本质是一个堆实现的。
优先级队列的内部是大小顶堆实现的，弹出pop()和队首top()都是获得堆首（根结点）的元素。
std::less<T>变成大顶堆（从上层到下层，堆元素是从大到小，同层之间随便）
std::greater<T>变成小顶堆（从上层到下层，堆元素是从小到大，同层之间随便）
基本操作有：
empty( ) //判断一个队列是否为空
pop( ) //删除队顶元素
push( ) //加入一个元素
size( ) //返回优先队列中拥有的元素个数
top( ) //返回优先队列的队顶元素
优先队列的时间复杂度为O（logn），n为队列中元素的个数，其存取都需要时间。
⼆叉堆是⼀种特殊的⼆叉树（完全⼆叉树），因为堆是基于完全二叉树，所以我们不需要用链式结构来表示，我们可以直接用数组存。
假设父节点的下表为parent，从父节点获取子节点：
左节点下标： 2*parent 1
右节点下标： 2*parent 2
假设子节点的下标为son(左右子节点都可以)：
父节点下标：(son-1)/2
小顶堆图示：
小顶堆的建立和删除都是 下沉 操作，添加做的是 上浮 操作。
大顶堆图示：
如上图所示，假设父节点的下标 parent=0，则其左子节点下标为Lchildren=2*parent 1。
右子节点下标为Rchildren=2*parent 2，如上示为例：
第 0 个数据的下标：parent = 0
第 1 个数据的下标：Lchildren = 2*parent 1 = 2*0 1 = 1
第 2 个数据的下标：Rchildren = 2*parent 2 = 2*0 2 = 2
⼀般的链表⼆叉树，我们操作节点的指针，⽽在数组⾥我们把数组索引作为指针。
问题描述
在c 17下，priority_queue优先级队列使用lambda表达式，可能遇到以下错误提示信息：
error: a lambda expression cannot appear in this context。
测试创建了一个自定义的优先级队列，测试代码如下：
代码语言：javascript复制#include <iostream>
#include <queue>
int main() {
std::cout << "hello test" << std::endl;
using Ty = std::pair<std::string,int>;
std::priority_queue<Ty,
std::vector<Ty>,
decltype( [](Ty a, Ty b)->bool{
return a.second > b.second;
})> q;
q.emplace(std::make_pair("yang",3));
q.emplace(std::make_pair("yong",2));
q.emplace(std::make_pair("zhen",1));
std::cout << "q.top()=" <<q.top().first <<std::endl;
return 0;
}这段代码在c 20下面测试是ok的。附测试网站地址：GDB online Debugger | Compiler - Code, Compile, Run, Debug online C, C
换成c 17下测试：
原因分析
Your code is valid C 20 as written but invalid C 17 or earlyer. 可能你使用了c 20的特性，在c 20之前不支持。
在 C 20 之前闭包类型不是默认可构造的。在 C 20 中没有捕获的闭包类型是默认可构造的。
参考这个回答： C : lambda-expression in unevaluated context
c 11 - C : lambda-expression in unevaluated context - Stack Overflow正在上传…重新上传取消https://stackoverflow.com/questions/52734311/c-lambda-expression-in-unevaluated-context
1.Lambda expressions are not allowed in unevaluated contexts (such as decltype) before C 20. 2.Closure types are not default constructible before C 20. In C 20 a closure type that has no capture is default constructible.
解决之道
问题原因清楚了，如何解决？不能轻易的就换成c 20的工具链吧。方法还是有的，可以改为仿函数实现。定义一个myGreater仿函数解决：
代码语言：javascript复制#include <iostream>
#include <queue>
using Ty = std::pair<std::string,int>;
struct myGreater {
bool operator() (Ty a, Ty b){
return a.second > b.second; //大顶堆
}
};
int main() {
std::cout << "hello test" << std::endl;
std::priority_queue<Ty,
std::vector<Ty>,
myGreater> q;
q.emplace(std::make_pair("yang",3));
q.emplace(std::make_pair("yong",2));
q.emplace(std::make_pair("zhen",1));
std::cout << "q.top()=" <<q.top().first <<std::endl;
return 0;
}如果使用std::greater这个默认的比较器会怎样？它仅比较pair的第一个元素。如上例假若改为
std::greater<Ty>,输出结果为："yang",不受第二个元素3,2,1的影响。
priority_queue()，默认按照从小到大排列。所以top()返回的是最大值而不是最小值！
使用greater<>后，数据从大到小排列，top()返回的就是最小值而不是最大值！
引用
c 优先队列(priority_queue)_STATICHIT静砸的博客-CSDN博客_c 优先队列
C 简单实现优先队列 - 简书
什么是二叉堆？_韩师学子--小倪的博客-CSDN博客_二叉堆
二叉堆 - 简书
通俗易懂，什么是二叉堆？_WrxDark的博客-CSDN博客_二叉堆
什么是二叉堆_「已注销」的博客-CSDN博客_二叉堆
