std::make_heap
定义于头文件 <algorithm>
|
||
(1) | ||
template< class RandomIt > void make_heap( RandomIt first, RandomIt last ); |
(C++20 前) | |
template< class RandomIt > constexpr void make_heap( RandomIt first, RandomIt last ); |
(C++20 起) | |
(2) | ||
template< class RandomIt, class Compare > void make_heap( RandomIt first, RandomIt last, |
(C++20 前) | |
template< class RandomIt, class Compare > constexpr void make_heap( RandomIt first, RandomIt last, |
(C++20 起) | |
在范围 [first, last)
中构造最大堆。函数第一版本用 operator< 比较元素,第二版本用给定的比较函数 comp
。
参数
first, last | - | 制作堆来源的元素范围 |
comp | - | 比较函数对象(即满足比较 (Compare) 要求的对象),若首个参数小于第二个,则返回 true 。 比较函数的签名应等价于如下: bool cmp(const Type1 &a, const Type2 &b); 虽然签名不必有 const & ,函数也不能修改传递给它的对象,而且必须接受(可为 const 的)类型 |
类型要求 | ||
-RandomIt 必须满足遗留随机访问迭代器 (LegacyRandomAccessIterator) 的要求。
| ||
-解引用 RandomIt 结果的类型必须满足可移动赋值 (MoveAssignable) 和可移动构造 (MoveConstructible) 的要求。
|
返回值
(无)
复杂度
至多 3*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 <functional> #include <vector> int main() { std::cout << "Max heap:\n"; std::vector<int> v { 3, 2, 4, 1, 5, 9 }; std::cout << "initially, v: "; for (auto i : v) std::cout << i << ' '; std::cout << '\n'; std::make_heap(v.begin(), v.end()); std::cout << "after make_heap, v: "; for (auto i : v) std::cout << i << ' '; std::cout << '\n'; std::pop_heap(v.begin(), v.end()); std::cout << "after pop_heap, v: "; for (auto i : v) std::cout << i << ' '; std::cout << '\n'; auto top = v.back(); v.pop_back(); std::cout << "former top element: " << top << '\n'; std::cout << "after removing the former top element, v: "; for (auto i : v) std::cout << i << ' '; std::cout << '\n' << '\n'; std::cout << "Min heap:\n"; std::vector<int> v1 { 3, 2, 4, 1, 5, 9 }; std::cout << "initially, v1: "; for (auto i : v1) std::cout << i << ' '; std::cout << '\n'; std::make_heap(v1.begin(), v1.end(), std::greater<>{}); std::cout << "after make_heap, v1: "; for (auto i : v1) std::cout << i << ' '; std::cout << '\n'; std::pop_heap(v1.begin(), v1.end(), std::greater<>{}); std::cout << "after pop_heap, v1: "; for (auto i : v1) std::cout << i << ' '; std::cout << '\n'; auto top1 = v1.back(); v1.pop_back(); std::cout << "former top element: " << top1 << '\n'; std::cout << "after removing the former top element, v1: "; for (auto i : v1) std::cout << i << ' '; std::cout << '\n'; }
输出:
Max heap: initially, v: 3 2 4 1 5 9 after make_heap, v: 9 5 4 1 2 3 after pop_heap, v: 5 3 4 1 2 9 former top element: 9 after removing the former top element, v: 5 3 4 1 2 Min heap: initially, v1: 3 2 4 1 5 9 after make_heap, v1: 1 2 4 3 5 9 after pop_heap, v1: 2 3 4 9 5 1 former top element: 1 after removing the former top element, v1: 2 3 4 9 5
参阅
将一个最大堆变成一个按升序排序的元素范围 (函数模板) | |
适配一个容器以提供优先级队列 (类模板) | |
实现 x > y 的函数对象 (类模板) |