命名空间
变体
操作

std::push_heap

来自 cppreference.com
< cpp‎ | algorithm
 
 
算法库
受约束的算法和范围上的算法 (C++20)
受约束的算法,例如 ranges::copy, ranges::sort, ...
执行策略 (C++17)
排序和相关操作
分区操作
排序操作
二分查找操作
(在已分区范围上)
集合操作(在已排序范围上)
合并操作(在已排序范围上)
堆操作
push_heap
最小/最大操作
(C++11)
(C++17)
字典序比较操作
排列操作
C 库
数值操作
未初始化内存操作
 
定义在头文件 <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 处的元素插入到 [firstlast - 1) 中。插入后,堆将变为 [firstlast)

1) 堆是相对于 operator<(直到 C++20)std::less{}(从 C++20 开始).
2) 堆是相对于 comp.

如果满足以下任何条件,行为未定义

  • [firstlast - 1) 不是相对于相应比较器的堆。
(直到 C++11)
(从 C++11 开始)

内容

[编辑] 参数

first, last - 插入后表示堆的范围
comp - 比较函数对象(即满足 Compare 要求的对象),如果第一个参数小于第二个参数,则返回 true.

比较函数的签名应等效于以下内容

bool cmp(const Type1& a, const Type2& b);

虽然签名不需要具有 const&,但函数不得修改传递给它的对象,并且必须能够接受类型 (可能是 const) Type1Type2 的所有值,无论值类别如何(因此,Type1& 不允许Type1 也不允许,除非对于 Type1 来说,移动等同于复制(从 C++11 开始))。
类型 Type1Type2 必须是这样的:类型 RandomIt 的对象可以被解引用,然后隐式转换为它们两者。

类型要求
-
RandomIt 必须满足 传统随机访问迭代器 的要求。
-
Compare 必须满足 Compare 的要求。

[编辑] 复杂度

给出 Nstd::distance(first, last)

1) 使用 operator<(直到 C++20)std::less{}(自 C++20 起) 进行比较,最多需要 log(N) 次比较。
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 [firstlast) 中的元素不需要是可交换的 必需

[编辑] 另请参阅

(C++11)
检查给定范围是否是最大堆
(函数模板) [编辑]
找到最大的最大堆子范围
(函数模板) [编辑]
从元素范围创建最大堆
(函数模板) [编辑]
从最大堆中移除最大元素
(函数模板) [编辑]
将最大堆转换为按升序排序的元素范围
(函数模板) [编辑]
向最大堆添加一个元素
(niebloid)[编辑]