std::
push_heap
函数模板 <algorithm>| default (1) | template <class RandomAccessIterator> void push_heap (RandomAccessIterator first, RandomAccessIterator last); |
| custom (2) | template <class RandomAccessIterator, class Compare>
void push_heap (RandomAccessIterator first, RandomAccessIterator last,
Compare comp); |
将元素加入堆
给定一个范围为[first,last-1)的堆，该函数通过将值放入堆中的相应位置， 将heap的范围扩展到[first,last)。
一个范围可以通过调用make_heap来组织成一个堆。 在此之后，如果使用push_heap和pop_heap分别添加和删除元素，则保留其堆属性。
☲ 参数
- first, last
- 指向新堆范围的初始和最终位置的随机访问迭代器,包括新加入的元素。使用的范围是[first,last)， 它包含first和last之间的所有元素，包括first指向的元素，但不包括last指向的元素。
- comp
-
二元函数，接受范围内的两个元素作为参数，
并返回一个可转换为bool类型的值。
返回的值表示返回的值表示作为第一个参数传递的元素是否被认为小于它定义的特定严格弱排序中的第二个。
函数不能修改它的任何参数。
它可以是函数指针，也可以是函数对象。
☉ 返回值
none.
☣ 示例
// range heap example
#include <iostream> // std::cout
#include <algorithm> // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap
#include <vector> // std::vector
int main () {
int myints[] = {10,20,30,5,15};
std::vector<int> v(myints,myints+5);
std::make_heap (v.begin(),v.end());
std::cout << "initial max heap : " << v.front() << '\n';
std::pop_heap (v.begin(),v.end()); v.pop_back();
std::cout << "max heap after pop : " << v.front() << '\n';
v.push_back(99); std::push_heap (v.begin(),v.end());
std::cout << "max heap after push: " << v.front() << '\n';
std::sort_heap (v.begin(),v.end());
std::cout << "final sorted range :";
for (unsigned i=0; i<v.size(); i++)
std::cout << ' ' << v[i];
std::cout << '\n';
return 0;
} |
输出:
initial max heap : 30
max heap after pop : 20
max heap after push: 99
final sorted range : 5 10 15 20 99
initial max heap : 30
max heap after pop : 20
max heap after push: 99
final sorted range : 5 10 15 20 99
✥ 复杂度
first and last之间的距离为对数:比较元素并可能交换(或移动)它们，直到重新排列为一个较长的堆。
⇄ 数据竞争
这个范围内的一些(或全部)对象被修改了。
☂ 异常安全性
如果任何元素比较，元素swap(或move)或迭代器操作抛出，则抛出。
注意，无效的参数会导致未定义的行为。
🍄 另请参阅
| make_heap | 从范围构建堆(函数模板) |
| pop_heap | 从堆范围中弹出元素(函数模板) |
| sort_heap | 对堆元素进行排序(函数模板) |
| reverse | 反转元素(函数模板) |