std::sort_heap
来自cppreference.com
| 定义于头文件 <algorithm>
|
||
| (1) | ||
| template< class RandomIt > void sort_heap( RandomIt first, RandomIt last ); |
(C++20 前) | |
| template< class RandomIt > constexpr void sort_heap( RandomIt first, RandomIt last ); |
(C++20 起) | |
| (2) | ||
| template< class RandomIt, class Compare > void sort_heap( RandomIt first, RandomIt last, Compare comp ); |
(C++20 前) | |
| template< class RandomIt, class Compare > constexpr void sort_heap( RandomIt first, RandomIt last, Compare comp ); |
(C++20 起) | |
转换最大堆 [first, last) 为以升序排序的范围。产生的范围不再拥有堆属性。
函数的第一版本用 operator< 比较元素，第二版本用给定的比较函数 comp 比较。
参数
| first, last | - | 要排序的元素范围 |
| comp | - | 比较函数对象（即满足比较 (Compare) 要求的对象），若首个参数小于第二个，则返回 true 。 比较函数的签名应等价于如下： bool cmp(const Type1 &a, const Type2 &b); 虽然签名不必有 const & ，函数也不能修改传递给它的对象，而且必须接受（可为 const 的）类型 |
| 类型要求 | ||
-RandomIt 必须满足值可交换 (ValueSwappable) 和 遗留随机访问迭代器 (LegacyRandomAccessIterator) 的要求。
| ||
-解引用 RandomIt 结果的类型必须满足可移动赋值 (MoveAssignable) 和可移动构造 (MoveConstructible) 的要求。
| ||
返回值
（无）
返回值
至多 2×N×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() 移除首元素
- 设
缺陷报告
下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。
| DR | 应用于 | 出版时的行为 | 正确行为 |
|---|---|---|---|
| LWG 2444 | C++98 | 复杂度要求在因子 2 上曾有错误 | 已更正 |
可能的实现
| 版本一 |
|---|
template< class RandomIt > void sort_heap( RandomIt first, RandomIt last ) { while (first != last) std::pop_heap(first, last--); } |
| 版本二 |
template< class RandomIt, class Compare > void sort_heap( RandomIt first, RandomIt last, Compare comp ) { while (first != last) std::pop_heap(first, last--, comp); } |
示例
运行此代码
#include <algorithm> #include <vector> #include <iostream> int main() { std::vector<int> v = {3, 1, 4, 1, 5, 9}; std::make_heap(v.begin(), v.end()); std::cout << "heap:\t"; for (const auto &i : v) { std::cout << i << ' '; } std::sort_heap(v.begin(), v.end()); std::cout << "\nsorted:\t"; for (const auto &i : v) { std::cout << i << ' '; } std::cout << '\n'; }
输出：
heap: 9 4 5 1 1 3 sorted: 1 1 3 4 5 9
参阅
| 从一个元素范围创建出一个最大堆 (函数模板) |
