std::push_heap
来自cppreference.com
![]() |
该页由英文版wiki使用Google Translate机器翻译而来。
该翻译可能存在错误或用词不当。鼠标停留在文本上可以看到原版本。你可以帮助我们修正错误或改进翻译。参见说明请点击这里. |
定义于头文件 <algorithm>
|
||
template< class RandomIt > void push_heap( RandomIt first, RandomIt last ); |
(1) | |
template< class RandomIt, class Compare > void push_heap( RandomIt first, RandomIt last, |
(2) | |
插入的位置处的元素到所定义的范围内
last-1
堆[first, last-1)
。 operator<的第一个版本的功能使用比较的元素,第二个使用给定的比较函数comp
.目录 |
[编辑] 参数
first, last | - | |
comp | - | 比较函数对象(即满足比较(Compare )要求的对象),若首个参数小于第二个,则返回 true 。比较函数的签名应等价于如下者: bool cmp(const Type1 &a, const Type2 &b); 签名不需要拥有 const & ,但函数对象必须不修改传递给它的对象。 |
类型要求 | ||
-RandomIt 必须满足 RandomAccessIterator 的要求。
| ||
-解引用 RandomIt 的类型必须满足 MoveAssignable 和 MoveConstructible 的要求。
|
[编辑] 返回值
[编辑] 复杂度
在大多数日志“2×(N)”比较N=std::distance(first, last).
原文:
At most 2×log(N) comparisons where 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> 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'; v.push_back(6); std::cout << "before push_heap: "; for (auto i : v) std::cout << i << ' '; std::cout << '\n'; std::push_heap(v.begin(), v.end()); std::cout << "after push_heap: "; for (auto i : v) std::cout << i << ' '; std::cout << '\n'; }
输出:
v: 9 5 4 1 1 3 before push_heap: 9 5 4 1 1 3 6 after push_heap: 9 5 6 1 1 3 4
[编辑] 另请参阅
将堆中的最大元素删除 (函数模板) |