std::push_heap
来自 cppreference.com
定义在头文件 <algorithm> 中 |
||
template< class RandomIt > void push_heap( RandomIt first, RandomIt last ); |
(1) | (从 C++20 开始为 constexpr) |
template< class RandomIt, class Compare > void push_heap( RandomIt first, RandomIt last, Compare comp ); |
(2) | (从 C++20 开始为 constexpr) |
将位置 last - 1 处的元素插入到 堆 [
first,
last - 1)
中。插入后,堆将变为 [
first,
last)
。
2) 堆是相对于 comp.
如果满足以下任何条件,行为未定义
-
[
first,
last - 1)
不是相对于相应比较器的堆。
|
(直到 C++11) |
(从 C++11 开始) |
内容 |
[编辑] 参数
first, last | - | 插入后表示堆的范围 |
comp | - | 比较函数对象(即满足 Compare 要求的对象),如果第一个参数小于第二个参数,则返回 true. 比较函数的签名应等效于以下内容 bool cmp(const Type1& a, const Type2& b); 虽然签名不需要具有 const&,但函数不得修改传递给它的对象,并且必须能够接受类型 (可能是 const) |
类型要求 | ||
-RandomIt 必须满足 传统随机访问迭代器 的要求。 | ||
-Compare 必须满足 Compare 的要求。 |
[编辑] 复杂度
给出 N 为 std::distance(first, last)
2) 对比较函数 comp 进行最多 log(N) 次应用。
[编辑] 示例
运行此代码
#include <algorithm> #include <iostream> #include <string_view> #include <vector> void println(std::string_view rem, const std::vector<int>& 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("after make_heap: ", v); v.push_back(6); println("after push_back: ", v); std::push_heap(v.begin(), v.end()); println("after push_heap: ", v); }
输出
after make_heap: 9 5 4 1 1 3 after push_back: 9 5 4 1 1 3 6 after push_heap: 9 5 6 1 1 3 4
[编辑] 缺陷报告
以下更改行为的缺陷报告被追溯应用于先前发布的 C++ 标准。
DR | 应用于 | 已发布的行为 | 正确行为 |
---|---|---|---|
LWG 3032 | C++98 | [ first, last) 中的元素不需要是可交换的 |
必需 |
[编辑] 另请参阅
(C++11) |
检查给定范围是否是最大堆 (函数模板) |
(C++11) |
找到最大的最大堆子范围 (函数模板) |
从元素范围创建最大堆 (函数模板) | |
从最大堆中移除最大元素 (函数模板) | |
将最大堆转换为按升序排序的元素范围 (函数模板) | |
(C++20) |
向最大堆添加一个元素 (niebloid) |