CKTIS / C++
std::is_heap — sprawdzanie własności kopca
std::is_heap sprawdza, czy zakres spełnia własność kopca, bez zmiany jego elementów. Domyślnie rozpoznaje kopiec maksymalny; własny komparator pozwala sprawdzać inny porządek, na przykład kopiec minimalny.
Wersja: C++23; repository compiler flag, production runtime not attested
Składnia
#include <algorithm>
std::is_heap(first, last)
std::is_heap(first, last, comp)std::is_heap z nagłówka <algorithm> zwraca bool, sprawdzając zakres [first, last). Potrzebuje poprawnego zakresu i iteratorów dostępu swobodnego, takich jak iteratory std::array lub std::vector. Nie buduje ani nie naprawia kopca i nie przestawia elementów. Zakres pusty lub jednoelementowy spełnia warunek.
Dla każdego indeksu dziecka i > 0 rodzic ma indeks (i - 1) / 2, z dzieleniem całkowitym. Warunek kopca wymaga, aby comp(parent, child) było false. Domyślne porównanie std::less{} oznacza dla liczb kopiec maksymalny: rodzic nie jest mniejszy od dziecka. std::greater<int>{} sprawdza kopiec minimalny. Komparator musi definiować ścisły słaby porządek; używaj tego samego porządku co przy budowaniu kopca.
Kopiec nie musi być posortowany: porządek między rodzeństwem nie jest wymagany. Koszt sprawdzania jest liniowy względem liczby elementów. Wynik odpowiada sprawdzeniu, czy std::is_heap_until(first, last, comp) == last; ta druga funkcja pomaga znaleźć pierwsze naruszenie. Do zbudowania kopca służy std::make_heap.
Przykład najpierw rozpoznaje kopiec maksymalny, następnie odrzuca go jako minimalny, a po przypisaniu values[3] = 10 wykrywa naruszenie relacji z rodzicem o wartości 5. Pokazane przeciążenia bez polityki wykonania są constexpr; dostępne są również przeciążenia z polityką wykonania. Wpis dotyczy C++23. Źródło jest rozwijanym szkicem standardu, a flaga kompilatora w repozytorium nie potwierdza środowiska produkcyjnego.
Przykłady
#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';
}
Wynik
true false false
Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.