Namespaces
Variants

    std::push_heap

    Von de.cppreference.net
     
    C++
     
    Algorithmenbibliothek
    Eingeschränkte Algorithmen und Algorithmen auf Bereichen (C++20)
    Eingeschränkte Algorithmen, z. B. ranges::copy, ranges::sort, ...
    Nicht-modifizierende Sequenzoperationen    
    Stapeloperationen
    (C++17)
    Suchoperationen
    Modifizierende Sequenzoperationen
    Kopieroperationen
    (C++11)
    (C++11)
    (C++11)
    Tauschoperationen
    Transformationsoperationen
    Erzeugungsoperationen
    Entfernungsoperationen
    Reihenfolgeändernde Operationen
    (bis C++17)(C++11)
    (C++20)(C++20)
    Stichprobenoperationen
    (C++17)

    Sortier- und verwandte Operationen
    Partitionierungsoperationen
    (C++11)    
    (C++11)

    Sortieroperationen
    Binäre Suchoperationen
    (auf partitionierten Bereichen)
    Mengenoperationen (auf sortierten Bereichen)
    Mischoperationen (auf sortierten Bereichen)
    Heap-Operationen
    Minimum-/Maximum-Operationen
    (C++11)
    (C++17)
    Lexikografische Vergleichsoperationen
    (C++20)
    Permutationsoperationen


     
    Definiert in Header <algorithm> 
    template< class RandomIt >
void push_heap( RandomIt first, RandomIt last );
    		(1) (constexpr seit C++20) 
    template< class RandomIt, class Compare >
void push_heap( RandomIt first, RandomIt last, Compare comp );
    		(2) (constexpr seit C++20)

    Fügt das Element an der Position last - 1 in den Heap [first, last - 1) ein. Der Heap nach dem Einfügen wird ein [first, last) sein.

    1) Der Heap ist bezüglich operator<(bis C++20)std::less{}(seit C++20).
    2) Der Heap ist bezüglich comp.

    Wenn eine der folgenden Bedingungen erfüllt ist, ist das Verhalten undefiniert:

    • [first, last - 1) ist kein Heap bezüglich des entsprechenden Vergleichs.
    (bis C++11)
    (seit C++11)

    Parameter

    first, last - das Paar von Iteratoren, das den Bereich der Elemente definiert, die nach dem Einfügen den binären Heap bilden
    comp - Vergleichsfunktionsobjekt (d. h. ein Objekt, das die Anforderungen von Compare erfüllt), das true zurückgibt, wenn das erste Argument kleiner als das zweite ist.

    Die Signatur der Vergleichsfunktion sollte der folgenden entsprechen:

    bool cmp(const Type1& a, const Type2& b);

    Obwohl die Signatur kein const& haben muss, darf die Funktion die ihr übergebenen Objekte nicht verändern und muss in der Lage sein, alle Werte des Typs (möglicherweise const) Type1 und Type2 unabhängig von der Wertkategorie zu akzeptieren (daher ist Type1& nicht erlaubt, auch nicht Type1 es sei denn, für Type1 ist eine Bewegung gleichbedeutend mit einer Kopie(seit C++11)).
    Die Typen Type1 und Type2 müssen so sein, dass ein Objekt vom Typ RandomIt dereferenziert und dann implizit in beide konvertiert werden kann.

    Typanforderungen
    -
    RandomIt muss die Anforderungen von LegacyRandomAccessIterator erfüllen.
    -
    Compare muss die Anforderungen von Compare erfüllen.

    Komplexität

    Gegeben N als std::distance(first, last):

    1) Höchstens log(N) Vergleiche mit operator<(bis C++20)std::less{}(seit C++20).
    2) Höchstens log(N) Anwendungen der Vergleichsfunktion comp.

    Beispiel

    Diesen Code ausführen
    #include <algorithm>
#include <iostream>
#include <string_view>
#include <vector>

void println(std::string_view rem, const std::vector<int>& v)
{
    std::cout << rem;
    for (int e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}

int main()
{
    std::vector<int> v{3, 1, 4, 1, 5, 9};
    
    std::make_heap(v.begin(), v.end());
    println("after make_heap: ", v);
    
    v.push_back(6);
    println("after push_back: ", v);
    
    std::push_heap(v.begin(), v.end());
    println("after push_heap: ", v);
}

    Ausgabe: 

    after make_heap: 9 5 4 1 1 3
after push_back: 9 5 4 1 1 3 6
after push_heap: 9 5 6 1 1 3 4

    Fehlerberichte

    Die folgenden verhaltensändernden Fehlerberichte wurden rückwirkend auf zuvor veröffentlichte C++-Standards angewendet.

    DR Angewendet auf Verhalten wie veröffentlicht Korrektes Verhalten
    LWG 3032 C++98 die Elemente von [first, last) mussten nicht austauschbar (swappable) sein erforderlich

    Siehe auch

    (C++11)
    		 prüft, ob der angegebene Bereich ein Max-Heap ist
    (Funktionsvorlage & Algorithmusfunktionsobjekt)
    (C++20)
    (C++11)
    		 findet den größten Unterbereich, der ein Max-Heap ist
    (Funktionsvorlage & Algorithmusfunktionsobjekt)
    (C++20)
    		erzeugt einen Max-Heap aus einem Bereich von Elementen
    (Funktionsvorlage & Algorithmusfunktionsobjekt)
    (C++20)
    		entfernt das größte Element aus einem Max-Heap
    (Funktionsvorlage & Algorithmusfunktionsobjekt)
    (C++20)
    		wandelt einen Max-Heap in einen aufsteigend sortierten Bereich von Elementen um
    (Funktionsvorlage & Algorithmusfunktionsobjekt)
    (C++20)
    (C++20)
    		 fügt ein Element zu einem Max-Heap hinzu
    (Algorithmusfunktionsobjekt)