std::
make_heap
函数模板 <algorithm>| default (1) | template <class RandomAccessIterator> void make_heap (RandomAccessIterator first, RandomAccessIterator last); |
| custom (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类型的值。
返回的值表示返回的值表示作为第一个参数传递的元素是否被认为小于它定义的特定严格弱排序中的第二个。
函数不能修改它的任何参数。
它可以是函数指针，也可以是函数对象。
☉ 返回值
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,last)内的对象被修改。
☂ 异常安全性
如果任何元素比较，元素swap(或move)或迭代器操作抛出，则抛出。
注意，无效的参数会导致未定义的行为。
🍄 另请参阅
| pop_heap | 从堆范围中弹出元素(函数模板) |
| push_heap | 将元素插入堆范围(函数模板) |
| sort_heap | 对堆元素进行排序(函数模板) |
| reverse | 反转元素(函数模板) |