WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C++

std::make_heap — einen Heap aus einem Bereich erstellen

std::make_heap ordnet einen Bereich in linearer Zeit zu einem Heap um. Standardmäßig steht das größte Element am Anfang; mit einem eigenen Vergleichsoperator lässt sich ein Min-Heap erstellen. Es ist nicht garantiert, dass der resultierende Bereich sortiert ist.

Version: C++23; repository compiler flag, production runtime not attested

Syntax

#include <algorithm>

namespace std {

template<class RandomAccessIterator>
constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
constexpr void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

} // namespace std

std::make_heap aus <algorithm> wandelt [first, last) in einen Heap um, ordnet seine Elemente neu und gibt void zurück. Der Bereich muss vorher kein Heap sein. Der Standardvergleich erstellt einen Max-Heap: Bei einem nicht leeren Bereich ist *first das größte Element. Der gesamte Bereich wird dadurch nicht sortiert; die genaue Anordnung der übrigen Elemente ist nicht festgelegt.

Die Überladung mit comp erstellt einen Heap gemäß diesem Vergleichsoperator. Für jedes Kind muss der Vergleich comp(parent, child) false ergeben. std::greater<int>{} aus <functional> erzeugt einen Min-Heap. Der Vergleichsoperator muss eine strikte schwache Ordnung definieren; verwende nicht <= anstelle von <.

Erforderlich sind Iteratoren mit wahlfreiem Zugriff sowie Elemente, die vertauscht, per Move konstruiert und per Move zugewiesen werden können. Für N = last - first führt der Algorithmus höchstens 3 * N Vergleiche aus; die Vergleichskomplexität ist also linear. Ein leerer Bereich ist zulässig, aber dann darfst du weder *first noch front() lesen.

Das Beispiel prüft den Heap-Wurzelwert und die Heap-Eigenschaft, statt eine bestimmte Anordnung aller Elemente vorauszusetzen. Behalte bei nachfolgenden Operationen dieselbe Ordnung bei: std::push_heap, std::pop_heap und std::sort_heap müssen einen kompatiblen Vergleichsoperator verwenden. std::pop_heap allein entfernt kein Element aus dem Container.

Beispiele

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{4, 1, 7, 3, 2};

    std::make_heap(values.begin(), values.end());
    std::cout << "max: " << values.front() << '\n';
    std::cout << std::boolalpha
              << "heap: " << std::is_heap(values.begin(), values.end()) << '\n';

    std::make_heap(values.begin(), values.end(), std::greater<int>{});
    std::cout << "min: " << values.front() << '\n';
}

Ergebnis

max: 7
heap: true
min: 1

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.

Quellen