std::make_heap
来自 cppreference.cn
定义于头文件 <algorithm> |
||
template< class RandomIt > void make_heap( RandomIt first, RandomIt last ); |
(1) | (C++20 起为 constexpr) |
template< class RandomIt, class Compare > void make_heap( RandomIt first, RandomIt last, Compare comp ); |
(2) | (C++20 起为 constexpr) |
在范围 [
first,
last)
中构造一个堆。
2) 构造的堆使用 comp。
如果满足以下任何条件,则行为是未定义的:
|
(C++11 前) |
|
(C++11 起) |
目录 |
[编辑] 参数
first, last | - | 定义要构成二叉堆的元素范围的迭代器对 |
comp | - | 比较函数对象(即满足比较 (Compare)要求的对象),如果第一个参数“小于”第二个,则返回true。 比较函数的签名应等效于以下内容 bool cmp(const Type1& a, const Type2& b); 虽然签名不需要包含 const&,但函数不得修改传递给它的对象,并且必须能够接受 |
类型要求 | ||
-RandomIt 必须满足遗留随机访问迭代器 (LegacyRandomAccessIterator)的要求。 | ||
-Compare 必须满足 Compare 的要求。 |
[编辑] 复杂度
给定 N 为 std::distance(first, last)
2) 最多 3N 次应用比较函数 comp。
[编辑] 示例
运行此代码
#include <algorithm> #include <functional> #include <iostream> #include <string_view> #include <vector> void print(std::string_view text, const std::vector<int>& v = {}) { std::cout << text << ": "; for (const auto& e : v) std::cout << e << ' '; std::cout << '\n'; } int main() { print("Max heap"); std::vector<int> v{3, 2, 4, 1, 5, 9}; print("initially, v", v); std::make_heap(v.begin(), v.end()); print("after make_heap, v", v); std::pop_heap(v.begin(), v.end()); print("after pop_heap, v", v); auto top = v.back(); v.pop_back(); print("former top element", {top}); print("after removing the former top element, v", v); print("\nMin heap"); std::vector<int> v1{3, 2, 4, 1, 5, 9}; print("initially, v1", v1); std::make_heap(v1.begin(), v1.end(), std::greater<>{}); print("after make_heap, v1", v1); std::pop_heap(v1.begin(), v1.end(), std::greater<>{}); print("after pop_heap, v1", v1); auto top1 = v1.back(); v1.pop_back(); print("former top element", {top1}); print("after removing the former top element, v1", v1); }
输出
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
[编辑] 缺陷报告
下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。
缺陷报告 | 应用于 | 发布时的行为 | 正确的行为 |
---|---|---|---|
LWG 3032 | C++98 | [ first, last) 的元素不需要可交换 |
需要 |
[编辑] 参阅
(C++11) |
检查给定的范围是否是一个最大堆 (函数模板) |
(C++11) |
寻找是一个最大堆的最大子范围 (函数模板) |
向一个最大堆添加一个元素 (函数模板) | |
从一个最大堆中移除最大的元素 (函数模板) | |
将一个最大堆转换成一个按升序排序的元素范围 (函数模板) | |
适配容器以提供优先级队列 (类模板) | |
(C++20) |
从一个元素范围创建一个最大堆 (算法函数对象) |