База знанияИзпитен център
BGБългарски
Избери език13

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

Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.

Източници