堆的概念、
堆的特性：
- 必须是完全二叉树
- 用数组实现
- 最大堆：根结点的键值是所有堆结点键值中最大者，且每个结点的值都比其孩子的值大。
- 最小堆：根结点的键值是所有堆结点键值中最小者，且每个结点的值都比其孩子的值小。
最大堆:
最小堆：
- 对于堆（Heap）这种数据结构，从根节点到任意结点路径上所有的结点都是有序的
STL堆算法、
1.make_heap()
template<class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
把指定范围内的元素生成一个堆。默认生成最大堆，可以传入第三个参数greater<>{}来生成最小堆。
2.pop_heap()
template<class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
- 作用是将一个最大堆中的最大元素放到堆的最后，并将剩余元素重新组织成一个新的最大堆
- 具体来说，
pop_heap将最大堆中的根节点元素（即堆中最大的元素）与堆的最后一个元素交换，然后将交换后的元素排除在堆的末尾。接着，pop_heap对剩余的元素进行重新排序，使其重新构成一个新的最大堆 - 把first和last-1交换，然后重新生成一个最大堆
- 可以使用容器的back来访问被弹出的元素，或使用pop_back进行删除
- 可以传入第三个参数greater<>{}来生成最小堆。
3.push_heap()
template<class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
- 假设first到last-1是一个有效堆，被加入堆的元素存放在last - 1的位置，重新生成堆
- 在使用该函数前，必须先把元素插入容器末尾
- 可以传入第三个参数greater<>{}来生成最小堆。
4.sort_heap()
template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);
template<class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);
对指定范围内的元素重新进行堆排序，默认升序排序，假设该序列是一个有序堆 ，时间复杂度是O（nlogn）。可以传入第三个参数greater<>{}来降序排序。
改进的算法ranges::、
ranges::make_heap 是 C++20 中引入的新算法，它也用于将元素序列转换为最大堆，但与 std::make_heap 不同，它是作为范围算法引入的，可以接受一个范围作为输入，而不是迭代器对。
ranges::make_heap 可以更方便地与其他范围算法组合使用，例如 ranges::sort 和 ranges::reverse，以对序列进行排序或反转操作。此外，它还支持传递一个可调用对象来定义元素之间的比较方式，以便生成最小堆。
#include<iostream>
using namespace std;
#include<algorithm>
#include<vector>
#include<list>
#include<ranges>
int main()
{
vector<int> v = {0,9,3,6,4,7,8,2};
//打印原始序列
auto print = [](const int& x){cout << x << " ";};
cout << "original vector :";
for_each(v.begin(),v.end(),print);
cout << endl;cout << ranges::is_heap(v) << endl;
//生成一个最大堆
ranges::make_heap(v);
cout << "after make heap vector :";
for_each(v.begin(),v.end(),print);
cout << endl;cout << ranges::is_heap(v) << endl;
//弹出最大堆第一个元素，然后重新排序
ranges::pop_heap(v);
v.pop_back();
cout << "after pop_back heap vector :";
for_each(v.begin(),v.end(),print);
cout << endl;cout << ranges::is_heap(v) << endl;
//添加一个元素到最大堆，然后重新排序
v.push_back(0);
ranges::push_heap(v);
cout << "after push_back heap vector :";
for_each(v.begin(),v.end(),print);
cout << endl;cout << ranges::is_heap(v) << endl;
//堆排序
ranges::sort_heap(v);
cout << "after sort heap vector :";
for_each(v.begin(),v.end(),print);
cout << endl;cout << ranges::is_heap(v) << endl;
return 0;
}
Comments NOTHING