Namespaces
Variants

std:: sort_heap

From cppreference.net
C++
Algorithm library
Constrained algorithms and algorithms on ranges (C++20)
Constrained algorithms, e.g. ranges::copy , ranges::sort , ...
Execution policies (C++17)
Non-modifying sequence operations
Batch operations
(C++17)
Search operations
Modifying sequence operations
Copy operations
(C++11)
(C++11)
(C++11)
Swap operations
Transformation operations
Generation operations
Removing operations
Order-changing operations
(until C++17) (C++11)
(C++20) (C++20)
Sampling operations
(C++17)

Sorting and related operations
Partitioning operations
Sorting operations
Binary search operations
(on partitioned ranges)
Set operations (on sorted ranges)
Merge operations (on sorted ranges)
Heap operations
sort_heap
(C++11)
(C++11)
Minimum/maximum operations
Lexicographical comparison operations
(C++20)
Permutation operations
C library
Numeric operations
Operations on uninitialized memory
Definiert im 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 wird nicht länger aufrechterhalten.

1) Der Heap ist bezüglich operator < (until C++20) std:: less { } (since C++20) und wird sortiert bezüglich operator < (until C++20) std:: less { } (since C++20) .
2) Der Heap bezieht sich auf comp und wird sortiert bezüglich comp .

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

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

Inhaltsverzeichnis

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 gegebene Bereich einen Max-Heap darstellt
(Funktions-Template)
(C++11)
findet den größten Teilbereich, der einen Max-Heap darstellt
(Funktions-Template)
erzeugt einen Max-Heap aus einer Reihe von Elementen
(Funktions-Template)
entfernt das größte Element aus einem Max-Heap
(Funktions-Template)
fügt ein Element zu einem Max-Heap hinzu
(Funktions-Template)
(C++20)
wandelt einen Max-Heap in eine aufsteigend sortierte Elementreihe um
(Algorithmus-Funktionsobjekt)