CKTIS / C++
std::is_heap — проверка на свойството на купчина
std::is_heap проверява дали даден диапазон удовлетворява свойството на купчина, без да променя елементите му. По подразбиране разпознава max-heap; собствен компаратор позволява проверка на друг ред, например min-heap.
Версия: C++23; repository compiler flag, production runtime not attested
Синтаксис
#include <algorithm>
std::is_heap(first, last)
std::is_heap(first, last, comp)std::is_heap, декларирана в <algorithm>, връща bool след проверка на диапазона [first, last). Необходими са валиден диапазон и итератори с произволен достъп, като тези на std::array или std::vector. Функцията не изгражда и не поправя купчина и не пренарежда елементите. Празен диапазон или диапазон с един елемент удовлетворява условието.
За всеки индекс на дете i > 0 индексът на родителя е (i - 1) / 2, като се използва целочислено деление. Условието за купчина изисква comp(parent, child) да е false. Сравнението по подразбиране std::less{} дава max-heap за числа: родителят не е по-малък от детето. std::greater<int>{} проверява min-heap. Компараторът трябва да определя строг слаб ред; използвайте същия ред, с който е изградена купчината.
Купчината не е задължително сортирана: не се изисква относителен ред между братята. Проверката има линейна сложност спрямо броя на елементите. Резултатът е еквивалентен на проверката std::is_heap_until(first, last, comp) == last; другата функция помага да се намери първото нарушение. Използвайте std::make_heap, за да изградите купчина.
Примерът първо разпознава max-heap, след това го отхвърля като min-heap и накрая открива нарушение спрямо родителя със стойност 5 след присвояването values[3] = 10. Показаните претоварвания без политика за изпълнение са constexpr; съществуват и претоварвания с политика за изпълнение. Този запис се отнася за C++23. Източникът е развиващ се проект на стандарт, а флагът на компилатора в хранилището не удостоверява производствената среда.
Примери
#include <algorithm>
#include <array>
#include <functional>
#include <iostream>
int main() {
std::array<int, 5> values{9, 5, 8, 1, 3};
std::cout << std::boolalpha;
std::cout << std::is_heap(values.begin(), values.end()) << '\n';
std::cout << std::is_heap(values.begin(), values.end(),
std::greater<int>{}) << '\n';
values[3] = 10;
std::cout << std::is_heap(values.begin(), values.end()) << '\n';
}
Резултат
true false false
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.