std::ranges::sort_heap
来自cppreference.com
定义于头文件 <algorithm>
|
||
调用签名 |
||
template< std::random_access_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity > |
(1) | (C++20 起) |
template< ranges::random_access_range R, class Comp = ranges::less, class Proj = std::identity > |
(2) | (C++20 起) |
转换最大堆 [first, last)
为按升序排序的范围。产生的范围不再拥有堆属性。
1) 用给定的二元比较函数
comp
与投影对象 proj
比较元素。2) 同 (1) ,但以
r
为范围,如同以 ranges::begin(r) 为 first
并以 ranges::end(r) 为 last
。此页面上描述的仿函数实体是 niebloid ,即:
实际上,它们能以函数对象,或以某些特殊编译器扩展实现。
参数
first, last | - | 要排序的元素范围 |
r | - | 要排序的元素范围 |
pred | - | 应用到投影后元素的谓词 |
proj | - | 应用到元素的投影 |
返回值
等于 last
的迭代器。
复杂度
给定 N = ranges::distance(first, last) ,至多比较 2Nlog(N) 次,投影 4Nlog(N) 次。
注解
最大堆是按照比较器 comp
与投影 proj
排列的元素范围 [f, l)
,拥有下列属性:
- 令 N == l - f ,对于所有
0 < i < N
, p == f[(i - 1) / 2] 和 q == f[i] ,表达式 std::invoke(comp, std::invoke(proj, p), std::invoke(proj, q)) 求值为 false 。 - 能用 ranges::push_heap() 在 𝓞(log N) 时间内添加新元素。
- 能用 ranges::pop_heap() 在 𝓞(log N) 时间内移除首元素。
- 令 N == l - f ,对于所有
可能的实现
struct sort_heap_fn { template< std::random_access_iterator I, std::sentinel_for<I> S, class Comp = ranges::less, class Proj = std::identity > requires std::sortable<I, Comp, Proj> constexpr I operator()( I first, S last, Comp comp = {}, Proj proj = {} ) const { auto ret {ranges::next(first, last)}; for (; first != last; --last) { ranges::pop_heap(first, last, comp, proj); } return ret; } template< ranges::random_access_range R, class Comp = ranges::less, class Proj = std::identity > requires std::sortable<ranges::iterator_t<R>, Comp, Proj> constexpr ranges::borrowed_iterator_t<R> operator()( R&& r, Comp comp = {}, Proj proj = {} ) const { return (*this)(ranges::begin(r), ranges::end(r), std::move(comp), std::move(proj)); } }; inline constexpr sort_heap_fn sort_heap{}; |
示例
运行此代码
#include <algorithm> #include <array> #include <iostream> void print(auto const& rem, auto const& v) { std::cout << rem; for (const auto i : v) std::cout << i << ' '; std::cout << '\n'; } int main() { std::array v {3, 1, 4, 1, 5, 9}; print("original array: ", v); std::ranges::make_heap(v); print("after make_heap: ", v); std::ranges::sort_heap(v); print("after sort_heap: ", v); }
输出:
original array: 3 1 4 1 5 9 after make_heap: 9 5 4 1 1 3 after sort_heap: 1 1 3 4 5 9
参阅
(C++20) |
检查给定范围是否为最大堆 (niebloid) |
(C++20) |
寻找能成为最大堆的最大子范围 (niebloid) |
(C++20) |
从一个元素范围创建出一个最大堆 (niebloid) |
(C++20) |
从最大堆中移除最大元素 (niebloid) |
(C++20) |
将一个元素加入到一个最大堆 (niebloid) |
将一个最大堆变成一个按升序排序的元素范围 (函数模板) |