1.实现方式
包含头文件 #include <algorithm>,通过vector和完全二叉树实现
建立堆make_heap(),在堆中添加数据push_heap(),在堆中删除数据pop_heap()和堆排序sort_heap():
2.make_heap()
inline void make_heap( b, e , cmp=greater<T>() )
make_heap()
是生成一个堆,大顶堆或小顶堆
make_heap(_RAIter,_RAIter)
默认生成大顶堆
make_heap(_RAIter,_RAIter,_Compare)
_Compare有两种参数,一种是greater(生成小顶堆),一种是less(生成大顶堆)。
make_heap()用于把一个可迭代容器变成一个堆,默认是大顶堆。
它有三个参数。第一个参数是指向开始元素的迭代器,第二个参数是指向最末尾元素的迭代器,第三个参数是less<>()或是greater<>(),前者用于生成大顶堆,后者用于生成小顶堆,第三个参数默认情况下为less<>(),less<int>()用于生成大顶堆。
3.push_heap()
push_heap()
是向堆中插入一个元素,并且使堆的规则依然成立
push_heap(_RAIter,_RAIter)
默认为大顶堆
push_heap(_RAIter,_RAIter,_Compare)
_Compare有两种参数,一种是greater(小顶堆),一种是less(大顶堆)
调用push_heap之前必须调用make_heap创建一个堆
首先数组push_back插入元素,然后再调用push_heap,它会使最后一个元素插到合适位置
注意,push_heap中的_Compare和make_heap中的_Compare参数必须是一致的,不然会插入堆失败,最后一个元素还是在最后位置,导致插入失败.
4.pop_heap()
inline void pop_heap(b,e,cmp=greater<T>() )
pop_heap()
是在堆的基础上,弹出堆顶元素。
pop_heap(_RAIter,_RAIter)
默认为大顶堆
pop_heap(_RAIter,_RAIter,_Compare)
_Compare有两种参数,一种是greater(小顶堆),一种是less(大顶堆)
比如pop_heap(nums.begin(), nums.end(),greater<int>())
,它会将堆顶元素(即为数组第一个位置)和数组最后一个位置对调,然后你可以调用数组pop_back,删除这个元素
注意,pop_heap中的_Compare和make_heap中的_Compare参数必须是一致的,不然会失败.
注意:在调用pop_heap函数后,若要实现元素真正从堆中删除,还需要调用底层容器的pop_back函数。
5.sort_heap
堆排序算法:inline void sort_heap(b,e,cmp=greater<T>() )