std::is_heap

Определён в заголовочном файле `<algorithm>`
template< class RandomIt > bool is_heap( RandomIt first, RandomIt last );	(1)	(начиная с C++11) (constexpr начиная с C++20)
template< class ExecutionPolicy, class RandomIt > bool is_heap( ExecutionPolicy&& policy, RandomIt first, RandomIt last );	(2)	(начиная с C++17)
template< class RandomIt, class Compare > bool is_heap( RandomIt first, RandomIt last, Compare comp );	(3)	(начиная с C++11) (constexpr начиная с C++20)
template< class ExecutionPolicy, class RandomIt, class Compare > bool is_heap( ExecutionPolicy&& policy, RandomIt first, RandomIt last, Compare comp );	(4)	(начиная с C++17)

Проверяет, является ли [first, last) кучей.

1) Проверяемое свойство кучи определяется относительно operator<(до C++20)std::less{}(начиная с C++20).

3) Проверяемое свойство кучи определяется относительно comp.

2,4) То же, что и (1,3), но выполняется согласно policy.

Эти перегрузки участвуют в разрешении перегрузки, только если значение следующего выражения равно true:

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>`	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>`	(начиная с C++20)

Параметры

first, last	-	пара итераторов, задающих диапазон проверяемых элементов
policy	-	политика выполнения, которую следует использовать
comp	-	объект функционального типа для сравнения (то есть объект, удовлетворяющий требованиям Compare), который возвращает `true`, если первый аргумент меньше второго. Сигнатура функции сравнения должна быть эквивалентна следующей: boolcmp(constType1&a,constType2&b); Хотя сигнатура не обязана содержать `const&`, функция не должна изменять переданные ей объекты и должна принимать любые значения типа (возможно, const) `Type1` и `Type2` независимо от категории значения (поэтому `Type1&` не допускается, как и `Type1`, за исключением случая, когда для `Type1` перемещение эквивалентно копированию(начиная с C++11)). Типы Type1 и Type2 должны быть такими, чтобы объект типа RandomIt можно было разыменовать, а полученное значение неявно преобразовать к обоим этим типам.
Требования к типам
-`RandomIt` должен соответствовать требованиям LegacyRandomAccessIterator.
-`Compare` должен соответствовать требованиям Compare.

Возвращаемое значение

true, если диапазон является кучей относительно соответствующего компаратора, и false в противном случае.

Сложность

Пусть \(\scriptsize N\)N — std::distance(first, last):

1,2) \(\scriptsize O(N)\)O(N) сравнений с использованием operator<(до C++20)std::less{}(начиная с C++20).

3,4) \(\scriptsize O(N)\)O(N) вызовов функции сравнения comp.

Исключения

Перегрузки с параметром шаблона с именем ExecutionPolicy сообщают об ошибках следующим образом:

Если выполнение функции, вызванной в рамках алгоритма, приводит к исключению и ExecutionPolicy является одной из стандартных политик, вызывается std::terminate. Для любого другого значения ExecutionPolicy поведение определяется реализацией.
Если алгоритму не удаётся выделить память, выбрасывается std::bad_alloc.

Пример

#include <algorithm>
#include <bit>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9};
    
    std::cout << "initially, v:\n";
    for (const auto& i : v)
        std::cout << i << ' ';
    std::cout << '\n';
    
    if (!std::is_heap(v.begin(), v.end()))
    {
        std::cout << "making heap...\n";
        std::make_heap(v.begin(), v.end());
    }
    
    std::cout << "after make_heap, v:\n";
    for (auto t{1U}; const auto& i : v)
        std::cout << i << (std::has_single_bit(++t) ? " | " : " ");
    std::cout << '\n';
}

Вывод:

initially, v:
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
making heap...
after make_heap, v:
9 | 6 9 | 5 5 9 7 | 1 1 3 5 8 3 4 2 |

См. также

is_heap_until (C++11)	находит наибольший поддиапазон, являющийся max-кучей (шаблон функции и функциональный объект алгоритма)
ranges::is_heap_until (C++20)
make_heap	создаёт max-кучу из диапазона элементов (шаблон функции и функциональный объект алгоритма)
ranges::make_heap (C++20)
push_heap	добавляет элемент в max-кучу (шаблон функции и функциональный объект алгоритма)
ranges::push_heap (C++20)
pop_heap	удаляет наибольший элемент из max-кучи (шаблон функции и функциональный объект алгоритма)
ranges::pop_heap (C++20)
sort_heap	преобразует max-кучу в диапазон элементов, отсортированных по возрастанию (шаблон функции и функциональный объект алгоритма)
ranges::sort_heap (C++20)
ranges::is_heap (C++20)	проверяет, является ли заданный диапазон max-кучей (функциональный объект алгоритма)

© cppreference.com
Licensed under the Creative Commons Attribution-ShareAlike Unported License v3.0.
https://en.cppreference.com/cpp/algorithm/is_heap