KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

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.

Bronnen