Namespaces
Variants

    std::sort_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
    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-/Maximumoperationen
    (C++11)
    (C++17)
    Lexikografische Vergleichsoperationen
    (C++20)
    Permutationsoperationen


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

    Wandelt den Heap [first, last) in einen sortierten Bereich um. Die Heap-Eigenschaft bleibt nicht erhalten.

    1) Der Heap bezieht sich auf operator<(bis C++20)std::less{}(seit C++20), und wird in Bezug auf operator<(bis C++20)std::less{}(seit C++20).
    2) Der Heap bezieht sich auf comp, und wird in Bezug auf comp.

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

    • [first, last) ist kein Heap.
    (bis C++11)
    (seit C++11)

    Parameter

    first, last - Das Paar von Iteratoren, das den Bereich des binären Heaps definiert, aus dem der sortierte Bereich erstellt werden soll
    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 äquivalent zu Folgendem sein:

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

    Obwohl die Signatur nicht const & benötigt, darf die Funktion die übergebenen Objekte nicht modifizieren und muss alle Werte der Typen (möglicherweise const) Type1 und Type2 unabhängig von der Wertkategorie akzeptieren können (daher ist Type1 & nicht erlaubt , ebenso wenig wie Type1 , es sei denn, für Type1 ist ein Move äquivalent zu einem Copy (seit C++11) ).
    Die Typen Type1 und Type2 müssen so beschaffen 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 2N⋅log(N) Vergleiche unter Verwendung von operator < (bis C++20) std:: less { } (seit C++20) .
    2) Höchstens 2N⋅log(N) Anwendungen der Vergleichsfunktion comp .

    Mögliche Implementierung

    sort_heap (1) 
    template<class RandomIt>
void sort_heap(RandomIt first, RandomIt last)
{
    while (first != last)
        std::pop_heap(first, last--);
}
    sort_heap (2) 
    template<class RandomIt, class Compare>
void sort_heap(RandomIt first, RandomIt last, Compare comp)
{
    while (first != last)
        std::pop_heap(first, last--, comp);
}
    *Hinweis: Der C++-Code in den `
    `-Tags wurde gemäß den Anforderungen nicht übersetzt. Die Funktionsnamen und C++-spezifischen Begriffe (wie "template", "class", "void", "while") bleiben unverändert.*

    Beispiel

    Diesen Code ausführen 
    #include <algorithm>
#include <iostream>
#include <string_view>
#include <vector>
void println(std::string_view fmt, const auto& v)
{
    for (std::cout << fmt; const auto &i : v)
        std::cout << i << ' ';
    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);
    std::sort_heap(v.begin(), v.end());
    println("after sort_heap, v: ", v);
}

    Ausgabe: 

    after make_heap, v: 9 4 5 1 1 3
after sort_heap, v: 1 1 3 4 5 9

    Fehlerberichte

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

    DR Angewendet auf Verhalten wie veröffentlicht Korrigiertes Verhalten
    LWG 2444 C++98 höchstens N⋅log(N) Vergleiche waren erlaubt erhöht auf 2N⋅log(N)

    Siehe auch

    (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)
    		erzeugt einen Max-Heap aus einem Bereich von Elementen
    (Funktionsschablone & Algorithmus-Funktionsobjekt)
    (C++20)
    		entfernt das größte Element aus einem Max-Heap
    (Funktionsschablone & Algorithmus-Funktionsobjekt)
    (C++20)
    		fügt ein Element zu einem Max-Heap hinzu
    (Funktionsschablone & Algorithmus-Funktionsobjekt)
    (C++20)
    (C++20)
    		 wandelt einen Max-Heap in einen sortierten Bereich von Elementen um
    (Algorithmus-Funktionsobjekt)