std::pop_heap

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

默认 (1)

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

自定义 (2)

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

从堆中弹出元素

重新排列堆范围 [first,last) 中的元素，使得被视为堆的部分缩短一个元素：具有最大值的元素被移动到 (last-1)。

当具有最大值的元素从 first 移动到 (last-1)（现在已移出堆）时，其他元素将被重新组织，使得范围 [first,last-1) 保持堆的性质。

可以通过调用 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: 从范围创建堆（函数模板）

push_heap: 将元素推入堆范围（函数模板）

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

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