CKTIS / C++
std::is_heap — die Heap-Eigenschaft prüfen
std::is_heap prüft, ob ein Bereich die Heap-Eigenschaft erfüllt, ohne seine Elemente zu verändern. Standardmäßig erkennt die Funktion einen Max-Heap; mit einem eigenen Vergleich lässt sich eine andere Ordnung prüfen, etwa ein Min-Heap.
Version: 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 aus <algorithm> gibt bool zurück und prüft den Bereich [first, last). Erforderlich sind ein gültiger Bereich und Random-Access-Iteratoren, wie sie std::array oder std::vector bereitstellen. Die Funktion erstellt oder repariert keinen Heap und ordnet die Elemente nicht um. Ein leerer Bereich oder ein Bereich mit einem Element erfüllt die Bedingung.
Für jeden Kindindex i > 0 lautet der Elternindex (i - 1) / 2, wobei ganzzahlig dividiert wird. Die Heap-Bedingung verlangt, dass comp(parent, child) false ist. Der Standardvergleich std::less{} ergibt bei Zahlen einen Max-Heap: Ein Elternknoten ist nicht kleiner als sein Kind. std::greater<int>{} prüft einen Min-Heap. Der Vergleich muss eine strikte schwache Ordnung festlegen; verwende dieselbe Ordnung wie beim Erstellen des Heaps.
Ein Heap muss nicht sortiert sein: Für Geschwister ist keine relative Ordnung vorgeschrieben. Die Prüfung hat lineare Komplexität bezogen auf die Anzahl der Elemente. Das Ergebnis entspricht der Prüfung std::is_heap_until(first, last, comp) == last; diese andere Funktion hilft, die erste Verletzung zu finden. Verwende std::make_heap, um einen Heap zu erstellen.
Das Beispiel erkennt zunächst einen Max-Heap, weist ihn dann als Min-Heap zurück und erkennt schließlich nach der Zuweisung values[3] = 10 eine Verletzung gegenüber dem Elternwert 5. Die gezeigten Überladungen ohne Ausführungsrichtlinie sind constexpr; Überladungen mit Ausführungsrichtlinie gibt es ebenfalls. Dieser Eintrag bezieht sich auf C++23. Die Quelle ist ein fortlaufend überarbeiteter Standardentwurf, und die Compiler-Option im Repository bestätigt nicht die Produktionslaufzeit.
Beispiele
#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';
}
Ergebnis
true false false
Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.