CKTIS / C++
std::pop_heap — die Heap-Wurzel ans Ende verschieben
std::pop_heap verschiebt die Wurzel eines nicht leeren Heaps ans Ende des Bereichs und stellt den Heap im verbleibenden Präfix wieder her. Es entfernt kein Element aus dem Container. Bei std::vector entfernt pop_back() das entnommene Element nur dann, wenn der Heap-Bereich am Ende des Vektors endet.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
#include <algorithm>
std::pop_heap(first, last);
std::pop_heap(first, last, comp);std::pop_heap aus <algorithm> arbeitet auf [first, last). Es verschiebt die ursprüngliche Wurzel nach last - 1 und stellt einen Heap in [first, last - 1) wieder her. Standardmäßig ist die Wurzel das größte Element. Die Überladung mit comp verwendet die angegebene Ordnungsrelation; beide Überladungen liefern void zurück.
Der Bereich muss bereits ein nicht leerer Heap unter derselben Ordnung sein. Die Iteratoren müssen wahlfreien Zugriff unterstützen, und die Elemente müssen sich vertauschen, per Move konstruieren und per Move zuweisen lassen. Der Komparator muss eine strikte schwache Ordnung definieren. Ein Aufruf mit einem leeren Bereich oder einem Bereich, der kein Heap ist, verletzt die Vorbedingungen.
Der Algorithmus verkleinert den Container nicht. Lies nach dem Aufruf das entnommene Element über *(last - 1) aus. Bei einem std::vector kannst du es nur dann mit back() auslesen und mit pop_back() entfernen, wenn last gleich end() des Vektors ist. Endet der Bereich früher, würden diese Aufrufe ein anderes Element auslesen und entfernen. Schließe das zuvor entnommene Element vor einem weiteren Aufruf aus dem Bereich aus. Die Anzahl der Vergleiche beträgt höchstens 2 * log2(N), wobei N = last - first gilt.
Das Beispiel erstellt mit std::make_heap einen Heap und gibt nur garantierte Ergebnisse aus, nicht die interne Anordnung des Heaps. Der gezeigte Code wurde unverändert ausgeführt, und seine Standardausgabe stimmte exakt mit der angegebenen Ausgabe überein. Als Quelle dient ein fortlaufend bearbeiteter Standardentwurf, nicht der eingefrorene C++23-Text.
Beispiele
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> values{4, 1, 7, 3};
std::make_heap(values.begin(), values.end());
std::pop_heap(values.begin(), values.end());
std::cout << "extracted=" << values.back() << '\n';
std::cout << "size_before=" << values.size() << '\n';
values.pop_back();
std::cout << "size_after=" << values.size() << '\n';
std::cout << "next=" << values.front() << '\n';
std::cout << "heap=" << std::boolalpha
<< std::is_heap(values.begin(), values.end()) << '\n';
}
Ergebnis
extracted=7 size_before=4 size_after=3 next=4 heap=true
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.