std::is_heap() algorithm
- since C++20
- since C++17
- since C++11
// (1)
template< class RandomIt >
constexpr bool is_heap( RandomIt first, RandomIt last );
// (2)
template< class RandomIt, class Compare >
constexpr bool is_heap( RandomIt first, RandomIt last, Compare comp );
// (3)
template< class ExecutionPolicy, class RandomIt >
bool is_heap( ExecutionPolicy&& policy, RandomIt first, RandomIt last );
// (4)
template< class ExecutionPolicy, class RandomIt, class Compare >
bool is_heap( ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp );
// (1)
template< class RandomIt >
bool is_heap( RandomIt first, RandomIt last );
// (2)
template< class RandomIt, class Compare >
bool is_heap( RandomIt first, RandomIt last, Compare comp );
// (3)
template< class ExecutionPolicy, class RandomIt >
bool is_heap( ExecutionPolicy&& policy, RandomIt first, RandomIt last );
// (4)
template< class ExecutionPolicy, class RandomIt, class Compare >
bool is_heap( ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp );
// (1)
template< class RandomIt >
bool is_heap( RandomIt first, RandomIt last );
// (2)
template< class RandomIt, class Compare >
bool is_heap( RandomIt first, RandomIt last, Compare comp );
Checks whether the elements in range [first
; last
) are a max heap.
-
(1) Elements are compared using
operator<
. -
(2) Elements are compared using the given binary comparison function
comp
. -
(3 - 4) Same as (1 - 2), but executed according to
policy
.Overload ResolutionThese overloads participate in overload resolution only if
std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>
(until C++20)std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>
(since C++20) istrue
.
Parameters
first 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). The signature of the comparison function should be equivalent to the following:
|
Type requirements
RandomIt | LegacyRandomAccessIterator |
Return value
true
if the range is a max heap, false
otherwise.
Complexity
Linear in the distance between first
and last
.
Exceptions
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 standard policies,std::terminate
is called. For any otherExecutionPolicy
, the behavior is implementation-defined. - If the algorithm fails to allocate memory,
std::bad_alloc
is thrown.
Notes
A max heap is a range of elements [f
; l
) that has the following properties:
- Given
N
asl - f
, for all0 < i < N
,f[(i - 1) / 2]
does not compare less thanf[i]
. - A new element can be added using
std::push_heap
, in O(log(N)) time. - The first element can be removed using
std::pop_heap
, in O(log(N)) time.
Examples
#include <algorithm>
#include <array>
#include <iostream>
int main()
{
const auto v = {1, 2, 3, 4};
for (int n : {3, 5})
(std::is_heap(v.begin(), v.end(), n) == std::end(v))
? std::cout << "v does not contain " << n << '\n'
: std::cout << "v contains " << n << '\n';
auto is_even = [](int i) { return i % 2 == 0; };
for (auto const& w : {std::array{3, 1, 4}, {1, 3, 5}})
if (auto it = std::is_heap_if(begin(w), end(w), is_even); it != std::end(w))
std::cout << "w contains an even number " << *it << '\n';
else
std::cout << "w does not contain even numbers\n";
}
v contains 3
v does not contain 5
w contains an even number 4
w does not contain even numbers
Hover to see the original license.