我要评论上一篇我们讲了栈和队列：它们不是容器，而是容器适配器——用一个现成容器封装转换出"后进先出 / 先进先出"的性质，默认的底层容器 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 各处，这一小节只是初次体会它的价值。
到此这篇关于c++ 如何把大顶堆改成小顶堆？priority_queue 与仿函数从原理到模拟实现的文章就介绍到这了,更多相关c++ priority_queue与仿函数内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！
发表评论