priority_queue 默认是大根堆，顶部元素最大；其第三个模板参数为比较类型，默认 std::less<int> 表示“小于”关系，但底层按最大堆维护，故需 std::greater<int> 才能得到小根堆。
priority_queue 默认是大根堆还是小根堆
默认是大根堆，也就是顶部元素最大。这容易让人误以为它像 Python 的 heapq 一样默认最小堆——不是的。priority_queue 的模板参数顺序和比较器逻辑刚好反直觉：第三个模板参数是「小于关系」的类型，但底层按「最大堆」维护，所以用 std::less（即 a ）时，大的排前面。
常见错误现象：priority_queue<int></int> 取出第一个元素却发现是最大值，而不是想要的最小值；调试半天才发现没换比较器。
- 要小根堆：显式传
std::greater<int></int>，写成priority_queue<int vector>, greater<int>></int></int> - 自定义类型必须提供可比较的
operator，或传入自定义比较函数对象（注意：函数对象类型要作为第三个模板参数，不能只传实参） - 不支持直接修改堆中某个元素——它不是可更新的堆结构，只能 push/pop
push 和 pop 的时间复杂度和线程安全
单次 push 和 pop 都是 O(log n)，内部用 vector 实现完全二叉树，没有额外分配开销。但它**完全不保证线程安全**：多个线程同时调用 push 或 top/pop 会直接导致未定义行为。
使用场景：适合单线程下做贪心、Dijkstra、Top-K 类任务；若需并发访问，得自己加锁（比如用 mutex 包住整个操作序列），别指望 STL 容器帮你扛。
立即学习“C++免费学习笔记（深入）”；
-
top()是O(1)，但返回的是 const 引用，不能通过它改值 -
empty()和size()是O(1)，放心用 - 没有
find、remove、update接口——真需要这些，考虑std::set或第三方库如boost::heap
自定义比较器写错的典型表现
写错比较器最常触发的是运行时崩溃或堆序错乱，比如 top() 返回异常值、pop() 后 size() 变负、甚至 abort()。根本原因是比较器没满足严格弱序（strict weak ordering）：不能有 a 为真，也不能出现 <code>a 这种环。
常见错误现象：插入几个元素后，top() 返回的不是预期极值；或者在不同编译器（如 GCC vs MSVC）下行为不一致。
- lambda 不能直接当模板参数（类型未知），必须用
decltype或封装成 struct - 结构体比较器里，
operator()必须是 const 成员函数 - 浮点数慎用
比较——优先用 <code>abs(a - b) 判断相等，再设计比较逻辑 - 字段为空指针时，解引用比较会崩；先判空再比
为什么不要用 deque 当底层容器
虽然 priority_queue 模板允许指定第二个参数为 deque，但实际几乎没人这么干——因为 deque 的随机访问性能不如 vector，而堆操作重度依赖 operator[] 计算父子节点索引（2*i+1, 2*i+2 等）。GCC 和 Clang 的实现都对 vector 做了缓存友好优化，换成 deque 后，push 平均慢 2–3 倍。
使用场景：仅当你要把 priority_queue 和已有 deque 共享内存池时才可能考虑，但代价远大于收益。
- 默认就是
vector，不用显写；显式写全模板参数时，第二个参数务必是vector<t></t> -
list更不行——不支持随机访问，编译不过 - 如果真想省 realloc 开销，可以
reserve()一次，但注意priority_queue不暴露底层容器，得从构造时传进去
堆不是万能容器，priority_queue 尤其不擅长动态调整中间元素。一旦需求里出现“修改某任务优先级”“按 ID 删除”“遍历所有元素”，就该立刻停下来，换数据结构。
