CKTIS / C++
std::is_heap — de heap-eigenschap controleren
std::is_heap controleert of een bereik aan de heap-eigenschap voldoet zonder de elementen te wijzigen. Standaard herkent de functie een max-heap; met een eigen comparator kun je een andere volgorde controleren, zoals die van een min-heap.
Versie: C++23; repository compiler flag, production runtime not attested
Syntax
#include <algorithm>
std::is_heap(first, last)
std::is_heap(first, last, comp)std::is_heap, gedeclareerd in <algorithm>, geeft bool terug nadat het bereik [first, last) is gecontroleerd. De functie vereist een geldig bereik en iterators met random access, zoals die van std::array of std::vector. Ze bouwt of repareert geen heap en herschikt de elementen niet. Een leeg bereik of een bereik met één element voldoet aan de voorwaarde.
Voor elke kindindex i > 0 is de ouderindex (i - 1) / 2, met gehele deling. De heap-voorwaarde vereist dat comp(parent, child) false is. De standaardvergelijking std::less{} levert voor getallen een max-heap op: een ouder is niet kleiner dan het kind. std::greater<int>{} controleert een min-heap. De comparator moet een strikte zwakke ordening definiëren; gebruik dezelfde ordening als bij het bouwen van de heap.
Een heap hoeft niet gesorteerd te zijn: er is geen onderlinge volgorde tussen broers vereist. De controle heeft een lineaire complexiteit ten opzichte van het aantal elementen. Het resultaat komt overeen met de test std::is_heap_until(first, last, comp) == last; die andere functie helpt de eerste schending te vinden. Gebruik std::make_heap om een heap te bouwen.
Het voorbeeld herkent eerst een max-heap, wijst die vervolgens af als min-heap en detecteert ten slotte een schending ten opzichte van de ouder met waarde 5 nadat values[3] = 10 is toegewezen. De getoonde overloads zonder uitvoeringsbeleid zijn constexpr; er bestaan ook overloads met uitvoeringsbeleid. Dit artikel betreft C++23. De bron is een voortdurend veranderend concept van de standaard, en de compileroptie in de repository bevestigt niet de productieomgeving.
Voorbeelden
#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';
}
Resultaat
true false false
De getoonde code en het opgegeven resultaat zijn in een geïsoleerde omgeving geverifieerd met de methode die in het verificatiebewijs voor exact deze versie is vastgelegd.