Namespaces
Variants

std:: push_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
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 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 der Einfügung wird [ 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 Vergleichsoperators.
(bis C++11)
(seit C++11)

Inhaltsverzeichnis

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 ä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 des Typs (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 eine Verschiebung äquivalent zu einer Kopie (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 log(N) Vergleiche unter Verwendung von 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 sein erforderlich

Siehe auch

(C++11)
prüft, ob der gegebene Bereich ein Max-Heap ist
(Funktions-Template)
(C++11)
findet den größten Teilbereich, der ein Max-Heap ist
(Funktions-Template)
erstellt einen Max-Heap aus einer Reihe von Elementen
(Funktions-Template)
entfernt das größte Element aus einem Max-Heap
(Funktions-Template)
wandelt einen Max-Heap in eine aufsteigend sortierte Elementreihe um
(Funktions-Template)
(C++20)
fügt ein Element zu einem Max-Heap hinzu
(Algorithmus-Funktionsobjekt)