std::make_heap
来自cppreference.com
| 在标头 <algorithm> 定义
|
||
| (1) | ||
| template< class RandomIt > void make_heap( RandomIt first, RandomIt last ); |
(C++20 前) | |
| template< class RandomIt > constexpr void make_heap( RandomIt first, RandomIt last ); |
(C++20 起) | |
| (2) | ||
| template< class RandomIt, class Compare > void make_heap( RandomIt first, RandomIt last, Compare comp ); |
(C++20 前) | |
| template< class RandomIt, class Compare > constexpr void make_heap( RandomIt first, RandomIt last, Compare comp ); |
(C++20 起) | |
在范围 [first, last)) 中构造堆。
1) 构造关于 operator< 的堆。
2) 构造关于 comp 的堆。
参数
| first, last | - | 堆的构造来源范围 |
| comp | - | 比较函数对象（即满足比较 (Compare) 要求的对象），如果首个参数小于 第二个，那么返回 true。 比较函数的签名应等价于如下： bool cmp(const Type1 &a, const Type2 &b); 虽然签名不必有 const &，函数也不能修改传递给它的对象，而且必须接受（可有 const 限定的）类型 |
| 类型要求 | ||
-RandomIt 必须符合老式随机访问迭代器 (LegacyRandomAccessIterator) 的要求。
| ||
-解引用 RandomIt 结果的类型必须满足可移动赋值 (MoveAssignable) 和可移动构造 (MoveConstructible) 的要求。
| ||
-Compare 必须符合比较 (Compare) 的要求。
| ||
返回值
（无）
复杂度
给定 N 为 std::distance(first, last)：
1) 应用最多 3N 次 operator< 进行比较。
2) 应用最多 3N 次比较函数 comp。
注解
关于 comp 的堆（最大堆）是拥有下列属性的随机访问范围 [first, last)：
- 给定 N 为 last - first，对于满足 0 < i < N 的所有整数 i，bool(comp(first[(i - 1) / 2], first[i])) 都是 false。
- 可以通过 std::push_heap 在 𝓞(log N) 时间内添加新元素。
- 可以通过 std::pop_heap 在 𝓞(log N) 时间内移除 *first。
示例
运行此代码
#include <algorithm> #include <functional> #include <iostream> #include <string_view> #include <vector> void print(std::string_view text, std::vector<int> const& v = {}) { std::cout << text << "："; for (const auto& e : v) std::cout << e << ' '; std::cout << '\n'; } int main() { print("最大堆"); std::vector<int> v{3, 2, 4, 1, 5, 9}; print("一开始，v", v); std::make_heap(v.begin(), v.end()); print("make_heap 后，v", v); std::pop_heap(v.begin(), v.end()); print("pop_heap 后，v", v); auto top = v.back(); v.pop_back(); print("之前的顶端元素", {top}); print("移除之前的顶端元素后，v", v); print("\n最小堆"); std::vector<int> v1{3, 2, 4, 1, 5, 9}; print("一开始，v1", v1); std::make_heap(v1.begin(), v1.end(), std::greater<>{}); print("make_heap 后，v1", v1); std::pop_heap(v1.begin(), v1.end(), std::greater<>{}); print("pop_heap 后，v1", v1); auto top1 = v1.back(); v1.pop_back(); print("之前的顶端元素", {top1}); print("移除之前的顶端元素后，v1", v1); }
输出：
最大堆： 一开始，v：3 2 4 1 5 9 make_heap 后，v：9 5 4 1 2 3 pop_heap 后，v：5 3 4 1 2 9 之前的顶端元素：9 移除之前的顶端元素后，v：5 3 4 1 2 最小堆： 一开始，v1：3 2 4 1 5 9 make_heap 后，v1：1 2 4 3 5 9 pop_heap 后，v1：2 3 4 9 5 1 之前的顶端元素：1 移除之前的顶端元素后，v1：2 3 4 9 5
缺陷报告
下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。
| 缺陷报告 | 应用于 | 出版时的行为 | 正确行为 |
|---|---|---|---|
| LWG 193 | C++98 | 堆要求 *first 是最大的元素 | 可以有等于 *first 的元素 |
| LWG 2166 | C++98 | 对堆的要求与最大堆的定义不够接近 | 改进要求 |
参阅
| 检查给定范围是否为一个最大堆 (函数模板) | |
| (C++11) |
查找能成为最大堆的最大子范围 (函数模板) |
| 将一个元素加入到一个最大堆 (函数模板) | |
| 从最大堆中移除最大元素 (函数模板) | |
| 将一个最大堆变成一个按升序排序的元素范围 (函数模板) | |
| 适配一个容器以提供优先级队列 (类模板) | |
| (C++20) |
从一个元素范围创建出一个最大堆 (niebloid) |