STL heap原理和用法
在C++ STL（标准模板库）中，heap（堆）并不是一个独立的容器，而是一组基于容器（通常是 vector）实现的算法函数，用于将一段数据组织成堆的数据结构形式，并提供了一些对堆进行操作的功能。以下是详细介绍：
一、堆的概念
- 完全二叉树：完全二叉树是一种特殊类型的二叉树，其中树的所有层级除了底层叶子节点都是满的，而最底层从左到右不得有空隙。
堆是一种特殊的完全二叉树数据结构，分为最大堆和最小堆两种形式：
- 最大堆：在最大堆中，每个节点的值都大于或等于它的子节点的值，所以根节点的值是整个堆中的最大值。例如，对于节点
A及其左右子节点B和C，有A >= B且A >= C，依此类推构建出整个树结构。 - 最小堆：与最大堆相反，每个节点的值都小于或等于它的子节点的值，根节点的值就是整个堆中的最小值。
堆的这种特性使得它在很多场景下非常有用，比如实现优先排序（优先级队列）、快速查找最值等，并且可以高效地进行插入和删除最值的操作。
测试代码
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
int ia[9] = {0,1,2,3,4,8,9,3,5};
vector<int> ivec(ia, ia+9);
make_heap(ivec.begin() , ivec.end());
cout<<is_heap(ivec.begin(), ivec.end())<<endl;
for(int i=0;i<ivec.size(); ++i)
{
cout<<ivec[i]<< " ";
}
cout<<endl;
ivec.push_back(7);
push_heap(ivec.begin() , ivec.end());
for(int i=0;i<ivec.size(); ++i)
{
cout<<ivec[i]<< " ";
}
cout<<endl;
pop_heap(ivec.begin() , ivec.end());
cout<<ivec.back()<<endl;
ivec.pop_back();
for(int i=0;i<ivec.size(); ++i)
{
cout<<ivec[i]<< " ";
}
cout<<endl;
sort_heap(ivec.begin() , ivec.end());
for(int i=0;i<ivec.size(); ++i)
{
cout<<ivec[i]<< " ";
}
cout<<endl;
return 0;
}
二、STL中与堆相关的函数
C++ STL在 <algorithm> 头文件中提供了以下几个主要的堆操作函数：
make_heap- 函数原型：
template< class RandomIt > void make_heap( RandomIt first, RandomIt last ); template< class RandomIt, class Compare > void make_heap( RandomIt first, RandomIt last, Compare comp );- 功能及参数说明：
这个函数用于将给定范围[first, last)内的数据构建成一个堆。默认情况下，它会构建一个最大堆，如果要构建最小堆，可以传入自定义的比较函数comp。其中first和last是随机访问迭代器，界定了要构建堆的数据范围，通常对应的是vector等容器中的一段元素区间。例如，使用vector来存储数据并构建堆：
#include <iostream> #include <algorithm> #include <vector> int main() { std::vector<int> myVector = {5, 3, 8, 1, 2}; std::make_heap(myVector.begin(), myVector.end()); // 默认构建最大堆 return 0; }
在上述代码中，myVector 中的元素原本是无序的，调用 make_heap 函数后，它们就被组织成了一个最大堆结构，此时 myVector 的第一个元素（myVector[0]）就是堆中的最大值（也就是整个 vector 区间元素的最大值）。
push_heap- 函数原型：
template< class RandomIt > void push_heap( RandomIt first, RandomIt last ); template< class RandomIt, class Compare > void push_heap( RandomIt first, RandomIt last, Compare comp );- 功能及参数说明：
该函数用于在已经是堆结构的数据末尾添加一个新元素后，将整个数据范围重新调整为堆结构。注意，使用这个函数前，需要先在容器末尾插入新元素（例如通过vector的push_back操作插入元素到vector末尾），然后再调用push_heap函数来调整堆。同样，默认构建最大堆，可通过传入比较函数构建最小堆。例如：
#include <iostream> #include <algorithm> #include <vector> int main() { std::vector<int> myVector = {5, 3, 8}; std::make_heap(myVector.begin(), myVector.end()); myVector.push_back(10); // 先在vector末尾插入新元素 std::push_heap(myVector.begin(), myVector.end()); // 再调整为堆结构 return 0; }
在这个示例中，先将 myVector 中的 5、3、8 构建成一个堆，然后添加新元素 10 到 vector 末尾，接着调用 push_heap 函数将 myVector 整体重新调整为堆结构，保证其依然满足堆的特性。
pop_heap- 函数原型：
template< class RandomIt > void pop_heap( RandomIt first, RandomIt last ); template< class RandomIt, class Compare > void pop_heap( RandomIt first, RandomIt last, Compare comp );- 功能及参数说明：
pop_heap函数用于将堆顶元素（在最大堆中是最大值，最小堆中是最小值）移动到给定范围[first, last)的末尾，然后调整剩余的元素范围[first, last - 1)使其重新成为一个堆。也就是说，它实际上并没有真正删除元素（只是将其移动到末尾了），如果要彻底删除这个元素，还需要结合容器自身的删除操作（比如vector的pop_back操作）。例如：
#include <iostream> #include <algorithm> #include <vector> int main() { std::vector<int> myVector = {8, 5, 3}; std::make_heap(myVector.begin(), myVector.end()); std::pop_heap(myVector.begin(), myVector.end()); // 将最大值8移到末尾 myVector.pop_back(); // 真正删除末尾的8 return 0; }
在这里，先构建了一个最大堆，然后调用 pop_heap 函数把堆顶的最大值 8 移到 vector 的末尾，最后通过 vector 的 pop_back 操作将其从 vector 中删除，实现了删除堆中最大值的效果。
sort_heap- 函数原型：
template< class RandomIt > void sort_heap( RandomIt first, RandomIt last ); template< class RandomIt, class Compare > void sort_heap( RandomIt first, RandomIt last, Compare comp );- 功能及参数说明：
sort_heap函数可以将一个已经是堆结构的范围[first, last)内的数据进行排序，排序后的数据就不再具有堆的结构特性了。它是利用堆的性质进行排序的一种高效方式，排序后的结果是一个递增（对于最小堆）或递减（对于最大堆）的有序序列。例如：
#include <iostream> #include <algorithm> #include <vector> int main() { std::vector<int> myVector = {8, 5, 3}; std::make_heap(myVector.begin(), myVector.end()); std::sort_heap(myVector.begin(), myVector.end()); for (int num : myVector) { std::cout << num << " "; } return 0; }
在上述代码中，先将 myVector 构建成一个最大堆，然后调用 sort_heap 函数对其进行排序，最后输出排序后的结果，可以看到元素按照从大到小的顺序排列，不过此时 myVector 不再是堆结构了。
is_heap- 函数原型：
template< class RandomIt > bool is_heap( RandomIt first, RandomIt last ); template< class RandomIt, class Compare > bool is_heap( RandomIt first, RandomIt last, Compare comp );- 功能及参数说明：
这个函数用于判断给定范围[first, last)内的数据是否已经构成了一个堆结构，可以根据默认规则（最大堆）或者传入的比较函数comp来进行判断，返回true表示是堆结构，返回false表示不是。例如：
#include <iostream> #include <algorithm> #include <vector> int main() { std::vector<int> myVector = {8, 5, 3}; std::make_heap(myVector.begin(), myVector.end()); std::cout << (std::is_heap(myVector.begin(), myVector.end())? "是堆结构" : "不是堆结构") << std::endl; return 0; }
在这个示例中，先构建堆后判断，会输出“是堆结构”，如果对 myVector 中的元素进行随意调整后再判断，就可能得到“不是堆结构”的结果。
三、适用场景与注意事项
-
适用场景
- 实现优先级队列：通过使用堆，可以方便地实现优先级队列，其中元素的优先级由堆的结构（最大堆或最小堆）来体现，比如任务调度系统中按照任务优先级来执行任务，就可以用堆来管理任务，每次取出堆顶元素（优先级最高的任务）进行处理。
- 高效获取最值及动态维护最值集合：在需要频繁查找一组数据中的最大值或最小值，并且数据集合可能会动态变化（插入或删除元素）的场景下，堆结构很合适。例如，实时监测一组传感器数据中的最值情况，随着新数据的不断传入（插入元素），可以通过堆快速更新最值信息，并且在需要移除最值时也能高效操作。
-
注意事项
- 容器要求：这些堆操作函数要求操作的容器必须提供随机访问迭代器，所以通常是和
vector配合使用较多，当然也可以是其他满足随机访问迭代器要求的容器，但像list等不支持随机访问迭代器的容器就不能直接使用这些函数了。 - 迭代器失效问题：和其他容器操作类似，在对容器进行插入、删除等操作改变了容器元素范围后，相关的迭代器可能会失效，后续再使用这些失效的迭代器去调用堆操作函数可能会导致错误结果，所以要留意在合适的时机更新迭代器或者重新获取正确的迭代器范围。
- 容器要求：这些堆操作函数要求操作的容器必须提供随机访问迭代器，所以通常是和
总之，STL中的堆相关函数为我们提供了方便地构建、操作和利用堆数据结构的手段，在很多涉及排序、最值处理以及优先级管理等编程场景中有着重要的应用价值。
优先级队列
优先级队列底层默认是一个maxheap , 而maxheap 底层是有vector表现出来的一个完全二叉树。
priority_queue也不是容器，是容器配接器(container adapter)
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int main()
{
//vector<int> arr;
//for(int i=0;i<9;++i)
//{
// arr.push_back(i);
//}
priority_queue<int> ipq(arr.begin() , arr.end());
int arr[9] = {0,1,2,3,4,5,6,7,8};
priority_queue<int> ipq(arr , arr+9);
cout<<ipq.size()<<endl;
for(int i = 0;i<9;++i)
{
cout<<ipq.top()<<" ";
}
cout<<endl;
while(!ipq.empty() )
{
cout<<ipq.top()<<" ";
ipq.pop();
}
cout<<endl;
return 0;
}
