std::make_heap

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

默认 (1)

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

自定义 (2)

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

将范围转换为堆

重排范围 [first,last) 中的元素，使其构成一个堆。

堆是一种组织范围元素的方式，它允许随时快速检索具有最高值的元素（使用 pop_heap），甚至可以重复检索，同时还允许快速插入新元素（使用 push_heap）。

具有最高值的元素始终由 first 指向。其他元素的顺序取决于具体实现，但在该头文件的所有堆相关函数中是一致的。

元素通过 operator<（对于第一个版本）或 comp（对于第二个版本）进行比较：具有最高值的元素是指在与范围中的任何其他元素进行比较时，该元素返回 false 的元素。

标准容器适配器 priority_queue 会自动调用 make_heap、push_heap 和 pop_heap 来维护容器的堆属性。

参数

first, last: 指向序列的初始位置和最终位置的随机访问迭代器，该序列将被转换为堆。使用的范围是 [first,last)，它包含 first 和 last 之间的所有元素，包括 first 指向的元素，但不包括 last 指向的元素。
RandomAccessIterator 应指向一个类型，该类型 swap 已正确定义，并且是可移动构造和可移动赋值的。
comp: 二元函数，它接受范围中的两个元素作为参数，并返回一个可转换为 bool 的值。返回的值指示第一个参数传递的元素在其定义的特定严格弱序中是否被认为小于第二个元素。
该函数不得修改其任何参数。
这既可以是函数指针，也可以是函数对象。

返回值

无

示例

// 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)内的对象将被修改。

异常

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

另见

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

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

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

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