std::pop_heap

定义于头文件 `<algorithm>`
template< class RandomIt > void pop_heap( RandomIt first, RandomIt last );	(1)
template< class RandomIt, class Compare > void pop_heap( RandomIt first, RandomIt last, Compare comp );	(2)

交换在位置 first 的值和在位置 last-1 的值，并令子范围 [first, last-1) 变为最大堆。这拥有从范围 [first, last) 所定义的堆移除首个（最大）元素的效应。

函数的首个版本使用 operator< 比较元素，第二版本使用给定的比较函数 comp 。

first, last	-	定义要修改的合法非空堆的元素范围
comp	-	比较函数对象（即满足比较 (`Compare`) 要求的对象），若首个参数小于第二个，则返回 true 。比较函数的签名应等价于如下者： bool cmp(const Type1 &a, const Type2 &b); 签名不需要拥有 const & ，但函数对象必须不修改传递给它的对象。类型 Type1 与 Type2 必须使得 RandomIt 类型的对象能在解引用后隐式转换到这两个类型。
类型要求
- `RandomIt` 必须满足 `ValueSwappable` 和 `RandomAccessIterator` 的要求。
- 解引用 `RandomIt` 结果的类型必须满足 `MoveAssignable` 和 `MoveConstructible` 的要求。

[编辑] 返回值

（无）

[编辑] 复杂度

至多 2×log(N) 次比较，其中 N=std::distance(first, last).

[编辑] 注意

一个最大堆是拥有下列属性的元素范围 [f,l) ：

设 N = l - f ，对于所有 0 < i < N ， f[floor(i-1 2)] 不比 f[i] 小。
新元素可用 std::push_heap() 添加
首元素可用 std::pop_heap() 移除

[编辑] 示例

运行此代码

#include <iostream>
#include <algorithm>
#include <vector>
 
int main()
{
    std::vector<int> v { 3, 1, 4, 1, 5, 9 };
 
    std::make_heap(v.begin(), v.end());
 
    std::cout << "v: ";
    for (auto i : v) std::cout << i << ' ';
    std::cout << '\n';
 
    std::pop_heap(v.begin(), v.end()); // 移动最大元素到结尾
 
    std::cout << "after pop_heap: ";
    for (auto i : v) std::cout << i << ' ';
    std::cout << '\n';
 
    int largest = v.back();
    v.pop_back();  // 实际移出最大元素
    std::cout << "largest element: " << largest << '\n';
 
    std::cout << "heap without largest: ";
    for (auto i : v) std::cout << i << ' ';
    std::cout << '\n';
}

输出：

v: 9 5 4 1 1 3 
after pop_heap: 5 3 4 1 1 9 
largest element: 9
heap without largest: 5 3 4 1 1

[编辑] 参阅

push_heap	将元素加入到堆 (函数模板) [编辑]
make_heap	根据区间内的元素创建出一个堆 (函数模板) [编辑]

语言
标准库头文件
概念
实用工具库
字符串库
容器库
算法库
迭代器库
数值计算库
输入/输出库
本地化库
正则表达式库 (C++11)
原子操作库 (C++11)
线程支持库 (C++11)
文件系统库 (C++17)
技术规范

cppreference.com

搜索

名字空间

变换

查看

操作