std::push_heap
来自cppreference.com
| 在标头 <algorithm> 定义
|
||
| (1) | ||
| template< class RandomIt > void push_heap( RandomIt first, RandomIt last ); |
(C++20 前) | |
| template< class RandomIt > constexpr void push_heap( RandomIt first, RandomIt last ); |
(C++20 起) | |
| (2) | ||
| template< class RandomIt, class Compare > void push_heap( RandomIt first, RandomIt last, Compare comp ); |
(C++20 前) | |
| template< class RandomIt, class Compare > constexpr void push_heap( RandomIt first, RandomIt last, Compare comp ); |
(C++20 起) | |
将位于位置 last - 1 的元素插入到堆 [first, last - 1) 中。堆在插入元素后就会是 [first, last)。
1) 堆是关于 operator< 的。
2) 堆是关于 comp 的。
如果 [first, last - 1) 不是堆，那么行为未定义。
参数
| 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) 应用最多 log(N) 次 operator< 进行比较。
2) 应用最多 log(N) 次比较函数 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 <iostream> #include <string_view> #include <vector> void println(std::string_view rem, std::vector<int> const& v) { std::cout << rem; for (int e : v) std::cout << e << ' '; std::cout << '\n'; } int main() { std::vector<int> v{3, 1, 4, 1, 5, 9}; std::make_heap(v.begin(), v.end()); println("make_heap 后：", v); v.push_back(6); println("push_back 后：", v); std::push_heap(v.begin(), v.end()); println("push_heap 后：", v); }
输出：
make_heap 后：9 5 4 1 1 3 push_back 后：9 5 4 1 1 3 6 push_heap 后：9 5 6 1 1 3 4
缺陷报告
下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。
| 缺陷报告 | 应用于 | 出版时的行为 | 正确行为 |
|---|---|---|---|
| LWG 193 | C++98 | 堆要求 *first 是最大的元素 | 可以有等于 *first 的元素 |
| LWG 2166 | C++98 | 对堆的要求与最大堆的定义不够接近 | 改进要求 |
参阅
| 检查给定范围是否为一个最大堆 (函数模板) | |
| (C++11) |
查找能成为最大堆的最大子范围 (函数模板) |
| 从一个元素范围创建出一个最大堆 (函数模板) | |
| 从最大堆中移除最大元素 (函数模板) | |
| 将一个最大堆变成一个按升序排序的元素范围 (函数模板) | |
| (C++20) |
将一个元素加入到一个最大堆 (niebloid) |