CKTIS / C++
std::push_heap — ein Element zu einem Heap hinzufügen
std::push_heap stellt die Heap-Eigenschaft wieder her, nachdem ein Element am Ende eines Bereichs angefügt wurde. Der Container wird dadurch nicht vergrößert: Das neue Element muss bereits an last - 1 stehen, und der vorherige Bereich muss ein gültiger Heap sein.
Version: C++23; repository compiler flag, production runtime not attested
Syntax
#include <algorithm>
std::push_heap(first, last);
std::push_heap(first, last, comp);std::push_heap aus <algorithm> fügt das Element an last - 1 in den Heap über [first, last) ein. Der Algorithmus fügt dem Container selbst kein Element hinzu und gibt void zurück. Üblicherweise ruft man zuerst push_back und danach std::push_heap mit den aktuellen Iteratoren auf.
Vor dem Aufruf muss [first, last - 1) unter derselben Ordnung bereits ein Heap sein. Der Bereich muss mindestens das neue Element enthalten; rufe den Algorithmus nicht für einen leeren Bereich auf. Um aus beliebigen Daten einen Heap zu erstellen, verwende std::make_heap statt eines einzelnen Aufrufs von std::push_heap.
Der Standardvergleich erzeugt einen Max-Heap: Das größte Element steht am Anfang. Die Überladung mit comp ändert die Ordnung; std::greater<int>{} erzeugt einen Min-Heap. Der Komparator muss eine strikte schwache Ordnung festlegen und zur Ordnung des vorhandenen Heaps passen. Ein Heap muss nicht sortiert sein.
Der Algorithmus benötigt Iteratoren mit wahlfreiem Zugriff. Die Elemente müssen sich vertauschen lassen, und ihr Typ muss Verschiebekonstruktion und Verschiebezuweisung unterstützen. Die Anzahl der Vergleiche beträgt O(log N), wobei N = last - first gilt; die Kosten des vorherigen push_back kommen gesondert hinzu. Im Beispiel ist {9, 5, 7} bereits ein Heap. Nach dem Anfügen von 12 genügt daher ein Aufruf, um die Heap-Eigenschaft wiederherzustellen.
Beispiele
#include <algorithm>
#include <iostream>
#include <vector>
int main() {
std::vector<int> heap{9, 5, 7};
heap.push_back(12);
std::push_heap(heap.begin(), heap.end());
std::cout << "top: " << heap.front() << '\n';
std::cout << "size: " << heap.size() << '\n';
std::cout << "is_heap: " << std::boolalpha
<< std::is_heap(heap.begin(), heap.end()) << '\n';
}
Ergebnis
top: 12 size: 4 is_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.