首页 > 代码库 > STL algorithm算法is_heap和is_heap_until(25)

STL algorithm算法is_heap和is_heap_until(25)

2024-07-22 20:43:37   222人阅读

is_heap原型：

std::is_heap

default (1)
template <class RandomAccessIterator>
  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 <iostream>
#include <vector>
#include <array>
#include <algorithm>
using namespace std;
void isheap(){
    vector<int> vi{1,2,3,4,5,6,7};
    vector<int> v2(vi.rbegin(),vi.rend());
    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 <class RandomAccessIterator>
  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 87 6 10 5 9

画成堆的结构如下：



可以看到，10是第一个破坏堆结构的元素，9也是，运行程序：

源代码：

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
using namespace std;
void isheapuntil(){
    vector<int> vi{9,8,7,6,10,5,9};
    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

——————————————————————————————————————————————————————————————————



STL algorithm算法is_heap和is_heap_until(25)


联系
我们