Namespaces
Variants

    std::pop_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    
    Batch-Operationen
    (C++17)
    Suchoperationen
    Modifizierende Sequenzoperationen
    Kopieroperationen
    (C++11)
    (C++11)
    (C++11)
    Tauschoperationen
    Transformationsoperationen
    Generierungsoperationen
    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 pop_heap( RandomIt first, RandomIt last );
    		(1) (constexpr seit C++20) 
    template< class RandomIt, class Compare >
void pop_heap( RandomIt first, RandomIt last, Compare comp );
    		(2) (constexpr seit C++20)

    Vertauscht den Wert an Position first mit dem Wert an Position last - 1 und macht den Teilbereich [first, last - 1) zu einem Heap. Dies hat die Wirkung, das erste Element aus dem Heap [first, last) zu entfernen.

    1) [first, last) ist ein Heap bezüglich operator<(bis C++20)std::less{}(seit C++20).
    2) [first, last) ist ein Heap bezüglich comp.

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

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

    Parameter

    first, last - das Iteratorpaar, das den nicht-leeren binären Heap Bereich von zu modifizierenden Elementen definiert (Wurzelelement extrahieren)
    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);

    Während die Signatur kein const& haben muss, darf die Funktion die übergebenen Objekte nicht modifizieren und muss alle Werte des Typs (möglicherweise const) Type1 und Type2 unabhängig von der Wertkategorie akzeptieren können (daher ist Type1& nicht erlaubt, noch ist Type1 erlaubt, es sei denn, für Type1 ist eine Verschiebung 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 2log(N) Vergleiche unter Verwendung von operator<(bis C++20)std::less{}(seit C++20).
    2) Höchstens 2log(N) Anwendungen der Vergleichsfunktion comp.

    Beispiel

    Diesen Code ausführen
    #include <algorithm>
#include <iostream>
#include <string_view>
#include <type_traits>
#include <vector>
 
void println(std::string_view rem, const auto& v)
{
    std::cout << rem;
    if constexpr (std::is_scalar_v<std::decay_t<decltype(v)>>)
        std::cout << v;
    else
        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);
    
    std::pop_heap(v.begin(), v.end()); // moves the largest to the end
    println("after pop_heap:  ", v);
    
    int largest = v.back();
    println("largest element: ", largest);
    
    v.pop_back(); // actually removes the largest element
    println("after pop_back:  ", v);
}

    Ausgabe: 

    after make_heap: 9 5 4 1 1 3
after pop_heap:  5 3 4 1 1 9
largest element: 9
after pop_back:  5 3 4 1 1

    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 1205 C++98 das Verhalten war unklar, wenn [first, last) leer ist das Verhalten ist in diesem Fall undefiniert

    Siehe auch

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