std::is_heap

Определено в заголовке `<algorithm>`
	(1)
template< class RandomIt > bool is_heap( RandomIt first, RandomIt last );		(с C++11) (до C++20)
template< class RandomIt > constexpr bool is_heap( RandomIt first, RandomIt last );		(с C++20)
template< class ExecutionPolicy, class RandomIt > bool is_heap( ExecutionPolicy&& policy, RandomIt first, RandomIt last );	(2)	(с C++17)
	(3)
template< class RandomIt, class Compare > bool is_heap( RandomIt first, RandomIt last, Compare comp );		(с C++11) (до C++20)
template< class RandomIt, class Compare > constexpr bool is_heap( RandomIt first, RandomIt last, Compare comp );		(с 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<.

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

2,4) Аналогично (1,3), но выполняется в соответствии с policy. Эти перегрузки не участвуют в разрешении перегрузки, если

`std::is_execution_policy_v<std::decay_t<ExecutionPolicy>>` является `true`.	(до C++20)
`std::is_execution_policy_v<std::remove_cvref_t<ExecutionPolicy>>` является `true`.	(с C++20)

Параметры

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

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

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

Сложность

Линейная относительно std::distance(first, last).

Исключения

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

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

Примечания

Куча относительно comp (куча с максимальным значением) — это произвольный доступный диапазон [first, last) с следующими свойствами:

Для \(N\)N как last - first, для всех целых i где \(0 < i < N\)0 < i < N, bool(comp(first[(i - 1) / 2], first[i])) является false.
Новый элемент можно добавить с помощью std::push_heap, за время \(\mathcal{O}(\log N)\)𝓞(log N).
*first можно удалить с помощью std::pop_heap, за время \(\mathcal{O}(\log N)\)𝓞(log N).

Пример

#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 |

Отчеты об ошибках

Следующие отчеты об ошибках, изменяющие поведение, были применены ретроактивно к ранее опубликованным стандартам C++.

DR	Применено к	Поведение при публикации	Корректное поведение
LWG 2166	C++11	требование кучи недостаточно точно соответствовало определению кучи с максимальным значением	улучшенное требование

См. также

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

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