堆不是一中sort ranges,堆中的元素不会以递增方式排列,内部以树状形式排列,该结构以每个结点小于等于父节点构成,优先队列就是以堆来实现
make_heap
//版本一:用operator <比较元素 template <class RandomAccessIterator> void make_heap(RandomAccessIterator first,RandomAccessIterator last); //版本二:用自定义的function object比较元素 template <class RandomAccessIterator,class StrictWeakOrdering> void make_heap(RandomAccessIterator first,RandomAccessIterator last,StrictWeakOrdering cmp);
push_heap
//版本一:用operator <比较元素 template <class RandomAccessIterator> void push_heap(RandomAccessIterator first,RandomAccessIterator last); //版本二:用自定义的function object比较元素 template <class RandomAccessIterator,class StrictWeakOrdering> void push_heap(RandomAccessIterator first,RandomAccessIterator last,StrictWeakOrdering cmp);
堆以[first,last-1)表示,新增加的元素为*(last-1);[first,last-1)为有效地range,也就是其不为空并且是一个堆
pop_heap
//版本一:用operator <比较元素 template <class RandomAccessIterator> void pop_heap(RandomAccessIterator first,RandomAccessIterator last); //版本二:用自定义的function object比较元素 template <class RandomAccessIterator,class StrictWeakOrdering> void pop_heap(RandomAccessIterator first,RandomAccessIterator last,StrictWeakOrdering cmp);
从堆中移除最大元素(即*first);[first,last-1)为有效地range,也就是其不为空;这两个版本的操作都有一个必然的结果:从堆中移除的元素是*(last-1),并且移除后为一个新堆
sort_heap
//版本一:用operator <比较元素 template <class RandomAccessIterator> void sort_heap(RandomAccessIterator first,RandomAccessIterator last); //版本二:用自定义的function object比较元素 template <class RandomAccessIterator,class StrictWeakOrdering> void sort_heap(RandomAccessIterator first,RandomAccessIterator last,StrictWeakOrdering cmp);
把堆转化为一个sorted ranges,不一定会保持等价元素的相对顺序
is_heap
//版本一:用operator <比较元素 template <class RandomAccessIterator> void is_heap(RandomAccessIterator first,RandomAccessIterator last); //版本二:用自定义的function object比较元素 template <class RandomAccessIterator,class StrictWeakOrdering> void is_heap(RandomAccessIterator first,RandomAccessIterator last,StrictWeakOrdering cmp);
测试一个序列是否是一个堆
#include <iostream> #include <vector> #include <iterator> #include <algorithm> using namespace std; int main() { vector<,,,,,,}; make_heap(v.begin(),v.end()-); for_each(v.begin(),v.end(),[](int i) { cout<<i<<" "; }); cout<<endl; push_heap(v.begin(),v.end()); for_each(v.begin(),v.end(),[](int i) { cout<<i<<" "; }); cout<<endl; cout<<is_heap(v.begin(),v.end())<<endl; sort_heap(v.begin(),v.end()); cout<<is_heap(v.begin(),v.end())<<endl; ; }