一、基础概念
priority_queue叫优先队列，底层不是队列，是堆（大顶堆 / 小顶堆），属于容器适配器。
适配器：不自己实现底层存储，复用别的容器（vector/deque）做底层，只在外层封装堆操作。 队列：先进先出；优先队列：优先级最高的元素先出，和入队顺序无关。
头文件：#include <queue>
// STL原型 template <class T, class Container = vector<T>, class Compare = less<T>> class priority_queue;三个模板参数：
T：存储元素类型Container：底层容器，默认vector<T>，要求支持[]、push_back、pop_backCompare：仿函数（二元谓词），默认less<T>，决定优先级规则- ⚠️ 最重要规则（和你手写仿函数完全一致）：
comp(a,b)返回 true →a 的优先级低于 b，b 要排在 a 前面 - 大顶堆要求：父节点应该大于等于子节点，当子节点 > 父节点的时候才交换。
默认传小于Less仿函数，大的优先级高
传大于Greater仿函数，小的优先级高
二、默认大顶堆原理：priority_queue<int>
默认：priority_queue<int, vector<int>, less<int>>less<int>：comp(a,b)=a < b
comp(parent, child)→parent < child返回 true：父优先级 < 子，子上浮- 堆顶是最大元素→大顶堆
小顶堆写法：
priority_queue<int, vector<int>, greater<int>> minHeap;greater<int>：comp(a,b)=a > b
堆顶是最小元素。
面试高频坑：less→ 大顶堆；greater→ 小顶堆，很多人记反！
三、底层堆原理（二叉堆，完全二叉树，数组存储）
用数组映射完全二叉树：
- 父节点下标：
parent - 左孩子：
2*parent +1 - 右孩子：
2*parent +2 - 子节点找父：
(child - 1)/2（整数除法向下取整）
堆的两个核心操作：
向上调整 adjust_up（插入 push）新元素插在数组末尾，不断和父节点比较；如果子优先级更高，交换父子，直到不满足条件 / 到根。
对应 push：
push_back+adjust_up(最后一个下标)向下调整 adjust_down（删除 pop）堆顶和末尾元素交换，
pop_back删掉堆顶；新堆顶向下不断和优先级更高的孩子交换，直到满足堆性质。对应 pop：首尾 swap + pop_back + adjust_down (0)
建堆（迭代器区间构造）从最后一个非叶子节点开始，向前依次向下调整。 最后一个非叶子节点下标：
(n-2)/2时间复杂度：O (n)，不是 O (nlogn)！
插入单个元素：O (logn)；删除堆顶：O (logn)；建堆：O (n)
四、priority_queue 常用接口
| 接口 | 作用 | 注意事项 |
|---|---|---|
push(x) | 插入元素，自动调整堆 | 底层 push_back + 向上调整 |
pop() | 删除堆顶（优先级最高元素） | 不返回堆顶元素！空队列调用 UB |
top() | 获取堆顶元素的引用 | 空队列调用 UB；const 引用 |
empty() | 判空 | bool |
size() | 返回元素个数 | size_t |
queue 的 front () 返回队首并 pop 分开；priority_queuepop()只删不取，top()只取不删。
#include <queue> int main() { priority_queue<int> max_pq; //大顶堆 max_pq.push(1); max_pq.push(9); max_pq.push(5); while(!max_pq.empty()) { cout << max_pq.top() << " "; max_pq.pop(); } //输出：9 5 1 return 0; }五、仿函数 Compare 深度理解
Compare comp是二元谓词仿函数，comp(a,b)返回 bool：
comp(a,b) == true ：a 优先级低于 b，b 应该放在 a 上方（堆中 b 优先级更高）
// less<T> bool operator()(const T& a,const T& b) { return a < b; }comp(p,c)→p < c→ true：父 p 优先级低于子 c → 交换上浮，大顶堆。
// greater<T> bool operator()(const T& a,const T& b) { return a > b; }comp(p,c)→p>c→ true：父 p 优先级低于子 c → 交换上浮，小顶堆。
记忆口诀：less是拿<比较，大顶堆greater拿>比较，小顶堆
六、容器适配器
一、什么是容器适配器
容器适配器（Container Adapter）本身不是独立容器，它是对已有容器的封装。适配器不自己开辟内存、不实现底层存储，复用底层容器的已有接口，对外只暴露一套新的、简化的接口，改变容器的行为。
一句话理解：适配器 = 套壳包装。底层容器负责存数据；适配器只提供特定访问规则。
一句话理解：适配器 = 套壳包装。底层容器负责存数据；适配器只提供特定访问规则。
STL 一共 3 个容器适配器：
stack栈：后进先出 LIFOqueue队列：先进先出 FIFOpriority_queue优先队列：优先级最高元素先出（堆）
| 适配器 | 默认底层容器 | 底层容器要求 |
|---|---|---|
| stack | deque<T> | 支持push_back/pop_back/back() |
| queue | deque<T> | 支持push_back/pop_front/back()/front() |
| priority_queue | vector<T> | 支持随机访问[]、push_back、pop_back（堆算法需要随机下标访问） |
适配器只是限制接口，不会新增存储能力。
二、三大适配器模板原型
1. stack
template< class T, class Container = deque<T> > class stack;对外接口：push()、pop()、top()、empty()、size()
只能在尾部操作：入栈、出栈、取栈顶，不能遍历、不能访问中间元素
2. queue
template< class T, class Container = deque<T> > class queue;对外接口：push()、pop()、front()、back()、empty()、size()
尾插、头删；只能取队首队尾，不能遍历中间元素
3. priority_queue
template< class T, class Container = vector<T>, class Compare = less<T> > class priority_queue;对外接口：push()、pop()、top()、empty()、size()
只允许取堆顶；push/pop 内部自动做堆调整。
三、底层容器更换规则
适配器可以手动更换底层容器，但必须满足接口要求
stack
底层可以用：deque/vector/list只要支持尾插尾删、back ()
stack<int, vector<int>> st;queue
底层不能用 vector！ queue 需要头删pop_front()，vector 的头删效率极低，而且 STL 不允许 vector 作为 queue 底层。 可选：deque、list
queue<int, list<int>> q;priority_queue
必须支持随机访问 []，堆调整需要按下标找父子节点 ✅ 允许：vector、deque❌ 禁止：list（没有随机访问）
priority_queue<int, deque<int>> pq;面试题：为什么 priority_queue 默认是 vector，stack/queue 默认 deque？ 答：
- vector 连续内存，随机访问快，最适合堆的下标操作；
- deque 头尾增删都是 O (1)，不需要移动大量元素，适合 stack、queue。
四、适配器的共性特点
- 没有迭代器！不能遍历适配器刻意隐藏底层容器迭代器。stack/queue/priority_queue 不提供 begin () /end ()。
设计目的：强制遵守数据结构规则。栈就只能栈顶操作，队列只能头尾操作，禁止乱序遍历。 如果你拿到迭代器，就可以随便修改中间元素，破坏栈 / 队列 / 堆的性质。
- 底层容器是适配器的成员就像你手写 priority_queue 里面：
Container _con;，所有操作都是调用_con的成员函数。 五、适配器对比表
表格
特性 stack queue priority_queue 规则 LIFO 后进先出 FIFO 先进先出 按优先级出队 默认底层 deque deque vector 插入位置 尾部 push_back 尾部 push_back 尾部 push_back + 向上堆调整 删除位置 尾部 pop_back 头部 pop_front 首尾交换 + pop_back + 向下堆调整 取元素 top () 栈顶 front () 队首 back () 队尾 top () 堆顶 迭代器 ❌无 ❌无 ❌无 模板参数 T, Container T, Container T, Container, Compare 仿函数
七、仿函数
仿函数本质：重载了operator()的类 / 结构体对象，可以像函数一样去调用。也叫函数对象。
1. 核心原理
普通函数调用：func(a,b)仿函数调用：obj(a,b)
看着像函数调用，实际是调用这个对象里重载的
operator()
template<class T> class Less { public: bool operator()(const T& x, const T& y) { return x < y; } };Less<int>是类Less<int>()是临时对象（匿名仿函数）com(a,b)等价com.operator()(a,b)
Less<int> lessObj; // 创建仿函数对象 cout << lessObj(2,5); // 等价 lessObj.operator()(2,5)，返回 true2. 仿函数 vs 普通函数
表格
| 仿函数（类重载 operator ()） | 普通函数 | |
|---|---|---|
| 状态 | 可以保存成员变量，携带状态 | 不能存状态 |
| 模板 | 容易和 STL 算法配合，类型推导友好 | 函数指针类型推导麻烦 |
| 内联 | 编译器更容易内联，效率高 | 容易退化成函数调用 |
写的
Less/Greater就是 STL 风格的谓词仿函数（返回 bool，两个参数 → 二元谓词）
3. 二元谓词规则
com(x,y)返回true的含义：
x 应该排在 y 的后面（y 优先级更高，y 放前面）
Less<int> com; com(x,y) → x < y 返回true // 含义：x比y小，x优先级更低，y更大，y要放到前面 → 降序排序Greater<int> com; com(x,y) → x > y 返回true // 含义：x比y大，x优先级更低，y更小，y放到前面 → 升序排序4. 仿函数两种使用方式
方式 1：匿名临时对象（你 main 里用的）
BubbleSort(a,7, Less<int>()); // Less<int>() 创建一个临时对象，传给模板参数Compare方式 2：先定义对象，再传入
Less<int> lessObj; BubbleSort(a,7, lessObj);5. 仿函数可以带状态
举个例子：统计比较次数
template<class T> class LessCount { public: int count = 0; bool operator()(const T& x, const T& y) { count++; // 记录调用次数 return x < y; } };手搓代码：
#pragma once #include<iostream> #include<vector> #include<assert.h> using namespace std; template<class T> class Less { public: bool operator()(const T& x, const T& y) { return x < y; } }; template <class T> class Greater { public: bool operator()(const T& x, const T& y) { return x > y; } }; namespace cl { template <class T,class Container = vector<T>,class Compare = Less<T>> class priority_queue { public: priority_queue() = default;//强制编译器生成默认构造 //用一段迭代器区间去进行初始化 template <class InputIterator> priority_queue(InputIterator first, InputIterator last) :_con(first,last) { //向下调整建堆 //向下调整建堆是从最后一个非叶子节点开始，即(_cin.size()-1-1)/2 这是一个父节点 for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--) { adjust_down(i); } } void push(const T& x) { _con.push_back(x); adjust_up(_con.size() - 1); } void pop() { assert(!empty()); swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); adjust_down(0); } const T& top() { assert(!empty()); return _con[0]; } bool empty() const { return _con.empty(); } size_t size() const { return _con.size(); } private: void adjust_up(int child) { Compare com; int parent = (child - 1) / 2; while (child > 0) { //if (_con[child] > _con[parent]) //if(_con[parent]<_con[child]) if (com(_con[parent], _con[child])) { swap(_con[child], _con[parent]); child = parent; parent = (child - 1)/2; } else { break; } } } void adjust_down(int parent) { //建立一个仿函数对象 Compare com; size_t child = 2 * parent + 1; while(child < _con.size()) { // 如果右孩子存在，并且右孩子比左孩子更满足比较规则，则child++选右孩子 //if (child + 1 < _con.size() && _con[child] < _con[child + 1]) if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) ++child; //if (_con[child] > _con[parent]) if (com(_con[parent], _con[child])) { swap(_con[child], _con[parent]); parent = child; child = 2 * parent + 1; } else break; } } private: Container _con; }; }
