C++ Algorithm is_heap_until()

C++ Algorithm is_heap_until() function is used to return an iterator pointing at the first element in the range [first, last) that does not satisfy the heap ordering condition, or end if the range forms a heap.

Elements are compared using operator< for the first version or using the given binary comparison function comp for the second version.

Syntax

  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);  

Parameter

first: A random access iterator pointing to the first element of a range to check for a heap.

last: A random access iterator pointing to the past last element in the range to check for a heap.

comp: A user defined binary predicate function that accepts two arguments and returns true if the two arguments are in order and false otherwise. It follows the strict weak ordering to order the elements.

Return value

It returns an iterator pointing at the first element in the range [first, last) that does not satisfy the heap ordering condition, or end if the range forms a heap.

Complexity

Complexity is linear in the distance between first and last: compares elements until a mismatch is found.

Data races

The objects in the range [first, last) are accessed.

Exceptions

This function throws an exception if either an element comparison or an operation on iterator throws an exception.

Note: The invalid parameters cause an undefined behavior.

Example 1

Let’s see the simple example to demonstrate the use of is_heap_until():

  #include <iostream>     // std::cout  #include <algorithm>    // std::is_heap_until, std::sort, std::reverse  #include <vector>       // std::vector    using namespace std;    int main () {    vector<int> foo {2,6,9,3,8,4,5,1,7};      sort(foo.begin(),foo.end());    reverse(foo.begin(),foo.end());      auto last = std::is_heap_until (foo.begin(),foo.end());      cout << “The ” << (last-foo.begin()) << ” first elements are a valid heap:”;    for (auto it=foo.begin(); it!=last; ++it)      cout << ‘ ‘ << *it;    cout << ‘n’;      return 0;  }  

Output:

The 9 first elements are a valid heap: 9 8 7 6 5 4 3 2 1

Example 2

Let’s see another simple example:

  #include <iostream>  #include <vector>  #include <algorithm>    using namespace std;    int main()  {    vector<int> v = {3, 1, 4};      cout << boolalpha;      cout << “before: is heap? ”              << (is_heap_until(v.begin(), v.end()) == v.end()) << endl;      make_heap(v.begin(), v.end());    cout << ” after: is heap? ”              << (is_heap_until(v.begin(), v.end()) == v.end()) << endl;                    return 0;  }  

Output:

before: is heap? false   after: is heap? true

Example 3

Let’s see another simple example:

  #include <iostream>  #include <vector>  #include <algorithm>    using namespace std;    bool ignore_case(char a, char b) {     return (tolower(a) == tolower(b));  }    int main(void) {     vector<char> v = {‘E’, ‘d’, ‘C’, ‘b’, ‘A’};     auto result = is_heap_until(v.begin(), v.end());       cout << char(*result) << ” is the first element which ”          << “does not satisfy the max heap condition.” << endl;       result = is_heap_until(v.begin(), v.end(), ignore_case);       if (result == end(v))        cout << “Entire range is a valid heap.” << endl;       return 0;  }  

Output:

d is the first element which does not satisfy the max heap condition.  Entire range is a valid heap.

Example 4

Let’s see a simple example:

  #include <iostream>  #include <vector>  #include <algorithm>    #include<iostream>   #include<algorithm> // for heap operations   using namespace std;   int main()   {               // Initializing a vector       vector<int> v1 = {40, 30, 25, 35, 15};               // Declaring heap iterator       vector<int>::iterator it1;               // Checking if container is heap       // using is_heap()       is_heap(v1.begin(), v1.end())?       cout << “The container is heap “:       cout << “The container is not heap”;       cout << endl;               // using is_heap_until() to check position        // till which container is heap       auto it = is_heap_until(v1.begin(), v1.end());             // Displaying heap range elements       cout << “The heap elements in container are : “;       for (it1=v1.begin(); it1!=it; it1++)          cout << *it1 << ” “;              return 0;   }  

Output:

The container is not heap  The heap elements in container are : 40 30 25

Next TopicC++ Algorithm

adjacent_find()algorithm any_of()beginners copy_if()copy()count_if()count()cpp equal()find_end()find_first_of()find_if_not() for_each()find_if()find()professionals tutorial

C++ algorithm is_heap_until() function

C++ Algorithm is_heap_until()

Syntax

Parameter

Return value

Complexity

Data races

Exceptions

Note: The invalid parameters cause an undefined behavior.

Example 1

Example 2

Example 3

Example 4

Underwriting of Shares

C++ Math abs() Functions

You may also like