std::push_heap

默认 (1)	template <class RandomAccessIterator> void push_heap (RandomAccessIterator first, RandomAccessIterator last);
自定义 (2)	template <class RandomAccessIterator, class Compare> void push_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

默认 (1)

template <class RandomAccessIterator>  void push_heap (RandomAccessIterator first, RandomAccessIterator last);

自定义 (2)

template <class RandomAccessIterator, class Compare>  void push_heap (RandomAccessIterator first, RandomAccessIterator last,                   Compare comp);

将元素推入堆范围

给定范围[first,last-1)中的一个堆，该函数通过将(last-1)中的值放置到其相应位置来将范围扩展为[first,last)。

可以通过调用make_heap将一个范围组织成一个堆。在此之后，如果使用push_heap和pop_heap分别从堆中添加和删除元素，其堆属性将得以保留。

参数

first, last: 随机访问迭代器指向新堆范围的起始和结束位置，包括被推入的元素。使用的范围是[first,last)，它包含first和last之间的所有元素，包括first指向的元素，但不包括last指向的元素。
comp: 二进制函数，它接受范围中的两个元素作为参数，并返回一个可转换为bool的值。返回的值指示第一个参数是否被认为在它定义的特定*严格弱序*中小于第二个参数。
除非[first,last)是空范围或只有一个元素的堆，否则此参数应与构建堆时使用的参数相同。
该函数不得修改其任何参数。
这可以是指针函数，也可以是函数对象。

返回值

无

示例

// 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

复杂度

复杂度为first和last之间距离的对数：比较元素并可能交换（或移动）它们，直到重新排列成一个更长的堆。

数据竞争

范围[first,last)中的一些（或全部）对象被修改。

异常

如果任何元素比较、元素交换（或移动）或迭代器操作抛出异常，则会抛出异常。
请注意，无效参数会导致未定义行为。

另见

make_heap: 从范围创建堆（函数模板）

pop_heap: 从堆范围中弹出元素（函数模板）

sort_heap: 对堆的元素进行排序（函数模板）

reverse: 反转范围（函数模板）