C++ Standard Library C++ STL Library

C++ <algorithm> - is_heap() Function



The C++ algorithm::is_heap function returns true if the range [first,last) forms a heap, as if constructed with make_heap.

The elements are compared using operator< (in first version) or comp (in second version).

Syntax

//default version
template <class RandomAccessIterator>
  bool is_heap (RandomAccessIterator first, RandomAccessIterator last);

//custom version  
template <class RandomAccessIterator, class Compare>
  bool is_heap (RandomAccessIterator first, RandomAccessIterator last,
                Compare comp);

Parameters

first Specify initial position of the random-access iterator. The range used is [first,last).
last Specify final position of the random-access iterator. The range used is [first,last).
comp A binary predicate that takes two elements in the range as arguments and returns a bool. The returned value indicates whether the first argument is considered to go before the second using the strict weak ordering it defines.

Return Value

Returns true if the range [first,last) is a heap (as if constructed with make_heap), false otherwise.

Time Complexity

Up to linear the distance between first and last i.e, Θ(n), where n is the distance between first and last.

Example:

In the example below, the algorithm::is_heap function is used to check a whether a given range of a vector forms a heap or not.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int main (){
  vector<int> vec{10, 5, 55, 22, 27, -10};
  vector<int>::iterator it;

  cout<<boolalpha;
  cout<<"vec contains:";
  for(it = vec.begin(); it != vec.end(); ++it)
    cout<<" "<<*it;

  //checking for heap
  cout<<"\nIs vec a heap: "<<
      is_heap(vec.begin(), vec.end()); 

  //make the vector a heap
  make_heap(vec.begin(), vec.end());

  cout<<"\n\nvec contains:";
  for(it = vec.begin(); it != vec.end(); ++it)
    cout<<" "<<*it;

  //checking for heap
  cout<<"\nIs vec a heap: "<<
      is_heap(vec.begin(), vec.end()); 

  return 0;
}

The output of the above code will be:

vec contains: 10 5 55 22 27 -10
Is vec a heap: false

vec contains: 55 27 10 22 5 -10
Is vec a heap: true

❮ C++ <algorithm> Library

5