上一篇我们讲了栈和队列：它们不是容器，而是容器适配器——用一个现成容器封装转换出"后进先出 / 先进先出"的性质，默认的底层容器 deque 用中控数组加一段段 buffer 实现了头尾高效插入删除。这一篇继续适配器家族的另一员：priority_queue（优先级队列）。它不遵循先进先出，而是优先级高的先出；它的底层不是普通容器那么简单，而是一个二叉堆。讲堆的模拟实现时，我们会遇到 C++ 中一个全新的重要概念——仿函数（函数对象），它是这一小节的重点，因为它能把"比较规则"从写死的代码中解放出来，用模板参数随时切换。
一、priority_queue 概述与使用
1.1 基本性质
template <class T, class Container = vector<T>, class Compare = less<T>> class priority_queue;
- 它也是容器适配器（container adapter），第二个模板参数是容器类型。
- 默认容器选择了
vector，而不是 deque：因为堆的底层算法需要大量的方括号访问（向上调整、向下调整全程都在[]），vector 的下标访问最极致。 - 优先级高的先出：优先级最高的就是最大（大堆）或最小（小堆）。默认是大堆，即默认先出最大的。
- 它本质就是数据结构里的堆，只是换了个名字；它同样不提供迭代器（自由访问会破坏"取堆顶"的性质）。
1.2 基本使用
priority_queue 在 queue 中，这一点需要强调一下，在写算法题的时候不要引错头文件
#include <queue> // priority_queue 在 <queue> 中
priority_queue<int> pq; // 默认大堆
pq.push(1);
pq.push(9);
pq.push(5);
pq.push(3);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
// 输出：9 5 3 1（降序，每次取最大）
| 接口 | 作用 |
|---|---|
push(x) |
入堆：尾插后向上调整 |
pop() |
删除堆顶：堆顶与最后一个交换、尾删、向下调整 |
top() |
取堆顶（优先级最高的元素，不删除） |
empty() / size() |
判空 / 元素个数 |
1.3 区间迭代器构造
除了逐个数 push，还可以用迭代器区间构造，它内部会直接建堆，比逐个 push（逐个向上调整）效率更好：
vector<int> v = {1, 9, 5, 3, 7};
priority_queue<int> pq(v.begin(), v.end());
// 原生数组也可以：连续物理空间下，原生指针就是天然迭代器
int arr[] = {1, 9, 5, 3, 7};
priority_queue<int> pq2(arr, arr + 5);
传原生指针的前提是底层连续物理空间（数组、vector 都满足），指针的
++、*天然就是迭代器的行为，sort、迭代区间构造都吃这一套。
1.4 换成小堆
默认 Compare = less<T>（用小于号实现大堆）。要取最小的元素，传 greater<T>：
less<T> 和 greater<T>：这俩是标准库的仿函数（函数对象），核心就是重载了 operator() 的比较器。
less<T>：a < b判断 a 是否小于 b，是就返回真。greater<T>：a > b判断 a 是否大于 b，是就返回真。
名字很好记：less = “小于”，greater = “大于”，和它们比较的方向一一对应。它们存在的意义是让"比较规则"成为一份可传入的数据（写进模板参数），而不是写死在堆代码里——这就是仿函数与后面要讲的调整算法衔接的关键。
// 传第三个模板参数，必须先传第二个（默认容器） priority_queue<int, vector<int>, greater<int>> pq; // 小堆 // 输出：1 3 5 7 9（升序，每次取最小）
注意一个反直觉的地方：默认大堆用的是小于（less），小堆反而用大于（greater）。堆的内部比较符号是写死的，我们要通过模板参数换仿函数来改变比较规则，而不是改代码。
二、堆算法回顾
priority_queue 的模拟实现依赖两个调整算法。先回忆堆的两条基本性质：逻辑上是完全二叉树，物理上是数组；父节点下标 (i-1)/2，左孩子 2*i+1，右孩子 2*i+2。
这几个公式里的 i 含义并不相同，别混用：(i-1)/2 里的 i 是孩子节点的下标，用它算父节点的下标；而 2*i+1、2*i+2 里的 i 是节点自身的下标，用它算左、右孩子的下标。方向正好相反：前者是"由孩子找父亲"（向上看），后者是"由父亲找孩子"（向下看）。记忆时抓住各自的服务对象：向上调整用 (i-1)/2，向下调整用 2*i+1 / 2*i+2。
2.1 向上调整（adjust up）：用于插入
插入新数据时先放在数组尾部（完全二叉树最后一个位置），然后与父节点比较，不满足堆的性质就交换，一路向上。假设已经是大堆，插入 8 后物理数组为 [9, 7, 5, 3, 8]，逻辑树如下，8 的父节点是 7，8 大于 7，交换后继续向上，最终调整为大堆：
调整后 8 换到 7 的位置，7 落到下一层，数组变为 [9, 8, 5, 3, 7]，仍然满足大堆。
要点：
- 从
size - 1（刚插入的位置）开始，父节点位置 =(child - 1) / 2。 - 大堆的条件：父小于孩子就交换（孩子向上走），交换后继续计算新的父节点。
- 最坏情况调整到根（
child == 0）或中途满足条件就结束。 - 不要记混公式：是"减一再除二"，不是"除二再减一"，拿具体下标（如 3、4）代入验证即可。
2.2 向下调整（adjust down）：用于删除
删除堆顶时不能直接挪动覆盖（会破坏元素间的父子关系），规则是：堆顶与最后一个元素交换，删除最后一个，再从根开始向下调整。
以删除大堆 [9, 8, 5, 3, 7] 的堆顶 9 为例，分三步：先交换堆顶与最后一个元素，数组变为 [7, 8, 5, 3, 9]；再尾删，得到 [7, 8, 5, 3]；然后从根开始向下调整，左右孩子 8、5 中 8 更大，7 小于 8 则交换，8 成为堆顶，数组变为 [8, 7, 5, 3]。
要点：
- 用假设法找左右孩子中大的那个：先假设左孩子大（
child = parent*2 + 1），若右孩子存在且右孩子大于左孩子，则++child指向右孩子。 - 判断右孩子存在必须用
child + 1 < size（完全二叉树有左孩子不一定有右孩子，不判断会越界）。 - 若父节点小于"大的孩子"就交换，父节点下移到孩子位置，继续找新孩子。
- 结束条件：
child >= size说明已经到叶子，调整结束。 - 这两个算法如果现在看着陌生，说明之前的堆学得不扎实，回去复习；看着图能自己写出来，才算掌握。
三、模拟实现 priority_queue
堆的封装只需要容器加两个调整算法。先不管仿函数，把核心逻辑写出来
#include <vector>
template <class T, class Container = vector<T>>
class priority_queue {
public:
void push(const T& x)
{
_con.push_back(x); // 尾插
adjust_up(_con.size() - 1); // 从新位置向上调整
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]); // 堆顶与最后一个交换
_con.pop_back(); // 删除最后一个
adjust_down(0); // 从根向下调整
}
const T& top() const { return _con[0]; } // 取堆顶
bool empty() const { return _con.empty(); }
size_t size() const { return _con.size(); }
private:
void adjust_up(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (_con[parent] < _con[child]) // 父小于孩子，孩子向上
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
void adjust_down(size_t parent)
{
size_t child = parent * 2 + 1; // 先假设左孩子
while (child < _con.size())
{
// 右孩子存在且大于左孩子，指向右孩子
if (child + 1 < _con.size() && _con[child] < _con[child + 1])
++child;
if (_con[parent] < _con[child]) // 父小于大的孩子，父向下
{
swap(_con[parent], _con[child]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
private:
Container _con;
};
关于"是否需要扩容"的疑问：容器是 vector 时它自己会扩容，是 deque 时开新 buffer——那是容器的事，适配器只负责调用 push_back，不关心底层怎么存储。这也正是封装的意义。
3.1 区间迭代器构造
直接复用上面的框架，加上区间构造：
template <class T, class Container = vector<T>>
class priority_queue {
public:
// 迭代器区间构造
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
while (first != last)
{
_con.push_back(*first);
++first;
}
// 从倒数第一个非叶子节点开始向下调整建堆
// 最后一个节点下标 size-1，它的父节点 = (size-1-1)/2 = (size-2)/2
for (int i = (int)(_con.size() - 2) / 2; i >= 0; --i)
adjust_down(i);
}
// ... 其余同前
};
- 逐个调用
push也能建堆，但那是 O(n log n) 的向上调整；从倒数第一个非叶子节点倒着向下调整是 O(n) 建堆，更快。 - 区间迭代器构造为什么不从根开始向上调整？两个算法的前提不同：
adjust_up要求当前节点上方（祖先链）已经是堆，适合push尾插；adjust_down要求当前节点的左右子树已经是堆，乱序数组的根不满足，所以从最后一个非叶子节点开始——它的孩子都是叶子、天然是堆，这一层处理完，上一层节点的子树就都合法了，逐层向上推到根，每一步的前提都成立。 - 注意
i用int而不是size_t：size_t是无符号，i >= 0永远成立，会死循环或越界。有符号无符号混用会刷一堆警告。
四、仿函数（函数对象）
4.1 概念：重载 operator() 的类
priority_queue 里比较符号是写死的（_con[parent] < _con[child]），大堆换小堆要改代码。C++ 不愿意像 C 语言那样用函数指针（写法繁琐、且函数指针不是类型，无法作为模板参数传递），于是引入了仿函数（functor，也叫函数对象）：
仿函数就是重载了
operator()的类（或结构体）。它的对象可以像函数一样被调用。
template <class T>
struct Less {
bool operator()(const T& x, const T& y) const
{
return x < y;
}
};
Less<int> lessFunc;
cout << lessFunc(1, 2) << endl; // 单看这行像函数调用，其实调用的是 operator()
// 本质：lessFunc.operator()(1, 2)
operator()重载的是函数调用运算符（圆括号，即函数调用时的参数列表括号），这是之前没遇到过的新运算符重载。- 与以前的重载（如
operator+参数个数、返回值基本固定）不同，operator()的参数个数和返回值都由需求决定，非常灵活：可以无参、可以任意多参数、返回值随功能而定。 - 用
struct还是class只有一点区别：默认访问权限不同（struct默认public，class默认private），其余都一样，都是类。 - 这一点对仿函数必须注意：
operator()是要被外部调用的（priority_queue 的调整算法、sort都会在类外调用它），所以必须是public。用struct天然满足；用class定义就必须显式写public:，否则编译报错（operator() is private within this context）。这也是标准库的less/greater都用struct定义的原因之一。
4.2 用模板参数控制比较：less 与 greater
库中提供了 less<T>（小于）和 greater<T>（大于）两个仿函数。把 priority_queue 里写死的比较换成仿函数对象：
template <class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue {
// ...
private:
void adjust_up(size_t child)
{
Compare comp; // 仿函数对象
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (comp(_con[parent], _con[child])) // 本质：comp.operator()(a, b)
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
// adjust_down 同理，把 _con[parent] < _con[child] 换成 comp(_con[parent], _con[child])
};
理解这条链路：
Compare是模板参数（一个类型）。缺省为less<T>，comp就是less<T>的对象，调用comp(a, b)等价于a < b。- 实例化时传
greater<T>，comp(a, b)就变成a > b，堆自动从大堆变成小堆。不用改任何代码，只换模板参数。 - 向上调整、向下调整里的比较逻辑全部由仿函数接管，其他部分一字不改。
priority_queue<int> pq1; // less -> 大堆 priority_queue<int, vector<int>, greater<int>> pq2; // greater -> 小堆
4.3 自定义仿函数：比较自定义类型
仿函数不止能切大堆小堆，还能自定义比较逻辑。比如往 priority_queue 里放 Date* 指针：默认 less<Date*> 比较的是地址大小，而地址大小随机（后 new 的不一定地址更大），运行几次结果都不一样。要按日期内容比较，自己写一个仿函数：
struct Date {
int _year, _month, _day;
bool operator<(const Date& d) const
{
if (_year != d._year) return _year < d._year;
if (_month != d._month) return _month < d._month;
return _day < d._day;
}
};
// 自定义仿函数：解引用后按日期内容比较
struct PDateLess {
bool operator()(Date* p1, Date* p2) const
{
return *p1 < *p2;
}
};
priority_queue<Date*, vector<Date*>, PDateLess> pq;
// 结果稳定：永远按日期排序，而不是按地址随机排序
仿函数在这里扮演的角色本质是回调：把"怎么比较"这个行为封装成对象传给 priority_queue，它需要比较时就调用你的 operator()。默认的 less/greater 不合适、或类型不支持比较时，都可以自己写一个仿函数控制。
4.4 一个细节：=default
自己写了区间迭代器构造后，编译器不再生成默认无参构造。想保留默认构造（priority_queue()），可以显式声明并强制编译器生成：
priority_queue() = default; // 强制编译器生成默认构造
这也印证了"只要写了任意构造函数，默认构造就消失"的规则——除非用 = default 请回来。
五、总结
这一篇学了 priority_queue 与仿函数。priority_queue 是适配器家族的第三员：容器适配器、默认容器 vector（堆算法需要大量下标访问）、默认大堆（less 小于号实现）、不提供迭代器。它的模拟实现只做两件事：push 尾插后向上调整，pop 堆顶与最后一个交换、尾删后向下调整，再加上区间构造的 O(n) 建堆。而真正的重点是仿函数：重载 operator() 的类，对象可以像函数一样调用；它本身是类型，可以走模板参数传递，于是"大堆还是小堆"、甚至"怎么比较自定义类型"，都从写死的代码变成了可配置的参数。仿函数此后会大量出现在排序、算法库、STL 各处，这一小节只是初次体会它的价值。
