STLalgorithm算法is_heap和is_heap_until(25)
is_heap原型:
std::is_heap
default (1)
template
bool is_heap (RandomAccessIterator first, RandomAccessIterator last);
custom (2)
template <class RandomAccessIterator, class Compare>
bool is_heap (RandomAccessIterator first, RandomAccessIterator last,
Compare comp);
测试范围内的元素是否是一个二叉堆。如果是,则返回true,否则返回false.
该函数使用operator<进行比较(也就是说,第一个版本测试是否是一个大顶堆)。(堆的概念自己去找)
如果范围内的元素个数少于两个,总是返回true,因为总能组成大顶堆。
一个简单的测试例子:(可以自己画出堆的完全二叉树图看看)
#include
#include
#include
#include
using namespace std;
void isheap(){
vector
vector
cout<<”vi=”;
for_each(vi.begin(),vi.end(),[](int i){cout<<i<<” “;});
cout<<endl;
if(is\_heap(vi.begin(),vi.end()))
cout<<"is\_heap(vi.begin(),vi.end()) return true!"<<endl;
else
cout<<"is\_heap(vi.begin(),vi.end()) return false!"<<endl;
cout<<"v2=";
for\_each(v2.begin(),v2.end(),\[\](int i){cout<<i<<" ";});
cout<<endl;
if(is\_heap(v2.begin(),v2.end()))
cout<<"is\_heap(v2.begin(),v2.end()) return true!"<<endl;
else
cout<<"is\_heap(v2.begin(),v2.end()) return false!"<<endl;
}
运行截图:
———————————————————————————————————————————————————
is_heap_until原型:
std::is_heap_until
default (1)
template
RandomAccessIterator is_heap_until (RandomAccessIterator first,
RandomAccessIterator last);
custom (2)
template <class RandomAccessIterator, class Compare>
RandomAccessIterator is_heap_until (RandomAccessIterator first,
RandomAccessIterator last
Compare comp);
该函数返回有效二叉堆的最末范围。
如果都有效,则返回last.
也就是说,返回第一个破坏二叉堆结构元素的迭代器。
例如一个序列:9 8 7 6 10 5 9
画成堆的结构如下:
可以看到,10是第一个破坏堆结构的元素,9也是,运行程序:
源代码:
#include
#include
#include
#include
using namespace std;
void isheapuntil(){
vector
cout<<”vi=”;
for_each(vi.begin(),vi.end(),[](int i){cout<<i<<” “;});
cout<<endl;
auto it=is\_heap\_until(vi.begin(),vi.end());
cout<<"it="<<\*it<<endl;
array<int,7> ai{9,8,7,6,5,4,3};
cout<<"ai=";
for\_each(ai.begin(),ai.end(),\[\](int i){cout<<i<<" ";});
cout<<endl;
auto it2=is_heap_until(ai.begin(),ai.end());
cout<<”it2=”<<*it2<<endl;
}
运行截图:
可以看到第一次返回的结果是10.
第二个vector里面都是有效堆,返回的则是last.
——————————————————————————————————————————————————————————————————
//写的错误或者不好的地方请多多指导,可以在下面留言或者点击左上方邮件地址给我发邮件,指出我的错误以及不足,以便我修改,更好的分享给大家,谢谢。
转载请注明出处:http://blog.csdn.net/qq844352155
author:天下无双
Email:coderguang@gmail.com
2014-9-16
于GDUT
——————————————————————————————————————————————————————————————————
- 本文作者: royalchen
- 本文链接: http://www.royalchen.com/2016/02/24/stlalgorithm算法is-heap和is-heap-until25/
- 版权声明: 本博客所有文章除特别声明外,均采用 MIT 许可协议。转载请注明出处!