命名空间
变体
操作

std::pop_heap

来自 cppreference.com
< cpp‎ | algorithm
 
 
算法库
受限算法和范围上的算法 (C++20)
受限算法,例如 ranges::copy, ranges::sort, ...
执行策略 (C++17)
排序和相关操作
分区操作
排序操作
二分搜索操作
(在分区范围内)
集合操作(在排序范围内)
合并操作(在排序范围内)
堆操作
pop_heap
最小/最大操作
(C++11)
(C++17)
词典比较操作
排列操作
C 库
数值操作
对未初始化内存的操作
 
定义在头文件 <algorithm>
template< class RandomIt >
void pop_heap( RandomIt first, RandomIt last );
(1) (从 C++20 开始为 constexpr)
template< class RandomIt, class Compare >
void pop_heap( RandomIt first, RandomIt last, Compare comp );
(2) (从 C++20 开始为 constexpr)

交换位置 first 的值和位置 last - 1 的值,并将子范围 [firstlast - 1) 变成堆。这将从堆 [firstlast) 中移除第一个元素。

1) [firstlast) 是一个相对于 operator<(直到 C++20)std::less{}(从 C++20 开始) 的堆。
2) [firstlast) 是一个相对于 comp 的堆。

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

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

内容

[编辑] 参数

first, last - 要修改的非空堆
comp - 比较函数对象(即满足 Compare 要求的对象),如果第一个参数小于第二个参数,则返回 true

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

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

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

类型要求
-
RandomIt 必须满足 LegacyRandomAccessIterator 的要求。
-
Compare 必须满足 Compare 的要求。

[编辑] 复杂度

假设 Nstd::distance(first, last)

1) 使用 operator<(直到 C++20)std::less{}(从 C++20 起) 进行比较,最多进行 2log(N) 次。
2) 对比较函数 comp 进行调用,最多进行 2log(N) 次。

[编辑] 示例

#include <algorithm>
#include <iostream>
#include <string_view>
#include <type_traits>
#include <vector>
 
void println(std::string_view rem, const auto& v)
{
    std::cout << rem;
    if constexpr (std::is_scalar_v<std::decay_t<decltype(v)>>)
        std::cout << v;
    else
        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);
 
    std::pop_heap(v.begin(), v.end()); // moves the largest to the end
    println("after pop_heap:  ", v);
 
    int largest = v.back();
    println("largest element: ", largest);
 
    v.pop_back(); // actually removes the largest element
    println("after pop_back:  ", v);
}

输出

after make_heap: 9 5 4 1 1 3
after pop_heap:  5 3 4 1 1 9
largest element: 9
after pop_back:  5 3 4 1 1

[编辑] 缺陷报告

以下行为变更缺陷报告被追溯应用于之前发布的 C++ 标准。

DR 应用于 已发布的行为 正确行为
LWG 1205 C++98 如果 [firstlast) 为空,则行为不明确。 在这种情况下,行为未定义。

[编辑] 另请参见

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