std::is_heap() and std::is_heap_until() in C++

In this tutorial, we will learn how to use the functions std::is_heap() and std::is_heap_until() in C++. You can use these functions to check whether a given list of elements is a heap or not. Also, you can find out in a given list of elements until which position the elements are a heap. The pre-requisites are basic knowledge of heap and vectors.

What is a heap?

Heap is a tree-based data structure, to organize the elements of a range based on the rule the greatest element is kept at the root and each node is lower than its parent. If we follow this rule then the heap is called max-heap. You can also arrange the elements such that every node must be lower than each of its children. If you follow this rule then the heap is called min-heap.

std::is_heap() and std::is_heap_until() functions

The std::is_heap() function checks whether a given list is a heap or not. You can simply use the vector.begin() and vector.end() to pass all the list-elements in the function.

vector<int> given_list = {100, 50, 45, 70, 72};
std::is_heap(given_list.begin(), given_list.end());

The is_heap() function returns 1 if the vector is a heap and 0 if it is not a heap.

The std::is_heap_until() function is used to find out in a given list of elements until which position the elements are a heap. We can use 2 iterators

vector<int> given_list = {100, 50, 45, 70, 72};
vector<int>::iterator iterator1;
vector<int>::iterator iterator2;
iterator2 = is_heap_until(given_list.begin(), given_list.end());

Then you can compare the iterators inside a ‘for’ loop and print the elements which follow heap rules.

C++ program for demonstrating the use of std::is_heap() and std::is_heap_until() functions

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{


  vector<int> given_list = {100, 50, 45, 70, 72};

  //declaring 2 vector iterators
  vector<int>::iterator iterator1;
  vector<int>::iterator iterator2;
  cout << "The given list is: ";
  for(iterator1 = given_list.begin();iterator1 != given_list.end();iterator1++)
    cout << *iterator1 << " ";

  cout << endl;
  // is_heap() returns 1 if the vector is a heap and 0
  // if it is not a heap.
  if(is_heap(given_list.begin(), given_list.end()) == 1)
    cout << "The given list is a heap " << endl;
  else
    cout << "The given list is not a heap" << endl;


  // we are using iterator2 with is_heap_until() 
  // to check the position
  // till which given list is a heap
  iterator2 = is_heap_until(given_list.begin(), given_list.end());


  cout << "The heap elements in given list are : ";
  for (iterator1=given_list.begin(); iterator1!=iterator2; iterator1++)
  cout << *iterator1 << " ";

  cout << endl;
  return 0;
}

Output for the above code

The given list is: 100 50 45 70 72 
The given list is not a heap
The heap elements in given list are : 100 50 45

Also, see:
std::extent() template in C++