Defined in header `<algorithm>` | ||
---|---|---|

template< class RandomIt > RandomIt is_heap_until( RandomIt first, RandomIt last ); | (1) | (since C++11) |

template< class ExecutionPolicy, class RandomIt > RandomIt is_heap_until( ExecutionPolicy&& policy, RandomIt first, RandomIt last ); | (2) | (since C++17) |

template< class RandomIt, class Compare > RandomIt is_heap_until( RandomIt first, RandomIt last, Compare comp ); | (3) | (since C++11) |

template< class ExecutionPolicy, class RandomIt, class Compare > RandomIt is_heap_until( ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp ); | (4) | (since C++17) |

Examines the range `[first, last)`

and finds the largest range beginning at `first`

which is a *max heap*.

1) Elements are compared using

`operator<`

.
3) Elements are compared using the given binary comparison function

`comp`

.
2,4) Same as (1,3), but executed according to

`policy`

. These overloads do not participate in overload resolution unless `std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`

is truefirst, last | - | the range of elements to examine |

policy | - | the execution policy to use. See execution policy for details. |

comp | - | comparison function object (i.e. an object that satisfies the requirements of `Compare` ) which returns `true` if the first argument is less than the second. The signature of the comparison function should be equivalent to the following:
The signature does not need to have |

Type requirements | ||

-`RandomIt` must meet the requirements of `RandomAccessIterator` . |

The upper bound of the largest range beginning at `first`

which is a *max heap*. That is, the last iterator `it`

for which range `[first, it)`

is a *max heap*.

Linear in the distance between `first`

and `last`

.

The overloads with a template parameter named `ExecutionPolicy`

report errors as follows:

- If execution of a function invoked as part of the algorithm throws an exception and
`ExecutionPolicy`

is one of the three standard policies,`std::terminate`

is called. For any other`ExecutionPolicy`

, the behavior is implementation-defined. - If the algorithm fails to allocate memory,
`std::bad_alloc`

is thrown.

A *max heap* is a range of elements `[f,l)`

that has the following properties:

- With
`N = l - f`

, for all`0 < i < N`

,`f[floor(`

does not compare less thani-1 2 `f[i]`

. - a new element can be added using
`std::push_heap()`

- the first element can be removed using
`std::pop_heap()`

#include <iostream> #include <algorithm> #include <vector> int main() { std::vector<int> v { 3, 1, 4, 1, 5, 9 }; std::make_heap(v.begin(), v.end()); // probably mess up the heap v.push_back(2); v.push_back(6); auto heap_end = std::is_heap_until(v.begin(), v.end()); std::cout << "all of v: "; for (auto i : v) std::cout << i << ' '; std::cout << '\n'; std::cout << "only heap: "; for (auto i = v.begin(); i != heap_end; ++i) std::cout << *i << ' '; std::cout << '\n'; }

Output:

all of v: 9 5 4 1 1 3 2 6 only heap: 9 5 4 1 1 3 2

(C++11) | checks if the given range is a max heap (function template) |

© cppreference.com

Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.

http://en.cppreference.com/w/cpp/algorithm/is_heap_until