Verwenden von STL-Heap-Algorithmen in C++

Mit C++-STL-Heap-Algorithmen können Sie einen Bereich von std::vector in einen Max-Heap umwandeln, sortieren oder seinen größten Wert ans Ende verschieben. std::pop_heap verschiebt den Wert; wenn Sie ihn aus dem Vektor entfernen möchten, müssen Sie ihn zusätzlich löschen.

Mit std::make_heap einen Bereich in einen Heap umwandeln

Ein Heap ist ein Bereich, dessen Elemente eine Eltern-Kind-Regel erfüllen. Beim standardmäßigen Vergleich erstellt std::make_heap einen Max-Heap: Jeder Elternknoten ist größer oder gleich seinen Kindern, daher steht der größte Wert am Anfang. In einem binären Heap auf Basis eines Vektors liegen die Kinder des Elements am Index i an den Positionen 2 * i + 1 und 2 * i + 2, sofern diese Positionen innerhalb des Bereichs liegen. Für einen Min-Heap verwenden Sie einen anderen Vergleich, zum Beispiel std::greater<int>.

std::make_heap ordnet die Elemente so um, dass sie die Heap-Eigenschaft erfüllen; der gesamte Bereich wird dadurch nicht sortiert. Viele Anordnungen können dieselbe Eigenschaft erfüllen. Der Code sollte sich daher auf den Wert am Anfang und die Eltern-Kind-Vergleiche stützen, nicht auf eine bestimmte Reihenfolge der Werte nach dem Aufruf.

Das folgende eigenständige Beispiel erstellt einen Heap und prüft die Eltern-Kind-Regel. Es wurde erfolgreich ausgeführt; die beobachtete Ausgabe ist unten zu sehen. Die unveränderten Beschriftungen in der Ausgabe sind auf Englisch.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{11, 82, 39, 72, 51, 32, 91};
    std::make_heap(values.begin(), values.end());

    bool is_max_heap = true;
    for (std::size_t child = 1; child < values.size(); ++child) {
        const std::size_t parent = (child - 1) / 2;
        if (values[parent] < values[child]) {
            is_max_heap = false;
            break;
        }
    }

    std::cout << "max-heap: " << std::boolalpha << is_max_heap << '\n';
    std::cout << "top: " << values.front() << '\n';
}

max-heap: true
top: 91

Das erste Element ist der oberste Wert des Heaps. Die Reihenfolge der übrigen Vektorelemente wird nur durch die Heap-Eigenschaft eingeschränkt. Sie sollten deshalb nicht als aufsteigend oder absteigend sortierte Liste verstanden werden.

Mit std::sort_heap einen Heap-Bereich sortieren

Rufen Sie std::sort_heap für einen Bereich auf, der bereits die Heap-Eigenschaft erfüllt. Beim standardmäßigen Vergleich ordnet die Funktion den Bereich aufsteigend. Danach erfüllt er die Heap-Eigenschaft nicht mehr. Rufen Sie daher erneut std::make_heap auf, bevor Sie eine Heap-Operation auf den gesamten Bereich anwenden.

Rufen Sie zum Beispiel nach std::make_heap(values.begin(), values.end()) std::sort_heap(values.begin(), values.end()) auf, um denselben Bereich zu sortieren. Der standardmäßige Vergleich ergibt eine aufsteigende Reihenfolge.

Die Überladung mit Vergleichsobjekt akzeptiert eine Funktion oder ein Funktionsobjekt, das die Reihenfolge festlegt. Verwenden Sie beim Erstellen und Sortieren eines Heaps denselben Vergleich. Ein mit std::greater<int> erstellter Heap muss beispielsweise auch mit diesem Vergleich sortiert werden. Die Standardüberladung eignet sich, wenn eine aufsteigende Ausgabe gewünscht ist.

Mit std::pop_heap das nächste Element im Heap entfernen

std::pop_heap verschiebt den obersten Wert an die letzte Position im Bereich und stellt die Heap-Eigenschaft im davorliegenden Bereich wieder her. Die Größe des Vektors ändert sich dadurch nicht. Um den Wert aus dem Container zu entfernen, rufen Sie nach std::pop_heap pop_back() auf.

Um ein Element hinzuzufügen, hängen Sie es an den Vektor an und rufen std::push_heap auf. Der Bereich vor dem angehängten Element muss bereits ein Heap sein; anschließend stellt std::push_heap die Heap-Eigenschaft für den erweiterten Bereich wieder her. Verwenden Sie für beide Algorithmen denselben Vergleich, der den Heap festlegt.

Das folgende eigenständige Beispiel prüft den verschobenen obersten Wert, löscht ihn separat und fügt anschließend ein Element hinzu, während die Heap-Eigenschaft erhalten bleibt. Es wurde erfolgreich ausgeführt; die beobachtete Ausgabe ist unten zu sehen. Die unveränderten Beschriftungen in der Ausgabe sind auf Englisch.

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

int main() {
    std::vector<int> values{11, 82, 39, 72, 51, 32, 91};
    std::make_heap(values.begin(), values.end());

    std::pop_heap(values.begin(), values.end());
    std::cout << "moved top: " << values.back() << '\n';
    values.pop_back();

    values.push_back(95);
    std::push_heap(values.begin(), values.end());
    std::cout << "new top: " << values.front() << '\n';
}

moved top: 91
new top: 95

Nach std::pop_heap bildet der Bereich bis vor dem letzten Element den Heap, den Sie weiterverwenden können. Sobald pop_back() den letzten Wert entfernt hat, enthält der Vektor wieder genau diesen Heap-Bereich. Wenn Sie ein Element anhängen, ohne diese Invariante zuvor sicherzustellen, erfüllen Sie die Vorbedingung von std::push_heap nicht.