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
Défini dans l'en-tête <algorithm>
template < class RandomIt >
void push_heap ( RandomIt first, RandomIt last ) ;
(1) (constexpr depuis C++20)
template < class RandomIt, class Compare >
void push_heap ( RandomIt first, RandomIt last, Compare comp ) ;
(2) (constexpr depuis C++20)

Insère l'élément à la position last - 1 dans le tas [ first , last - 1 ) . Le tas après l'insertion sera [ first , last ) .

1) Le tas est par rapport à operator < (jusqu'en C++20) std:: less { } (depuis C++20) .
2) Le tas est relatif à comp .

Si l'une des conditions suivantes est satisfaite, le comportement est indéfini :

  • [ first , last - 1 ) n'est pas un tas par rapport au comparateur correspondant.
(jusqu'à C++11)
(depuis C++11)

Table des matières

Paramètres

first, last - la paire d'itérateurs définissant la plage d'éléments qui forment le tas binaire après insertion
comp - objet fonction de comparaison (c'est-à-dire un objet qui satisfait aux exigences de Compare ) qui retourne true si le premier argument est inférieur au second.

La signature de la fonction de comparaison doit être équivalente à ce qui suit :

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

Bien que la signature n'ait pas besoin d'avoir const & , la fonction ne doit pas modifier les objets qui lui sont passés et doit pouvoir accepter toutes les valeurs de type (éventuellement const) Type1 et Type2 indépendamment de la catégorie de valeur (ainsi, Type1 & n'est pas autorisé , pas plus que Type1 sauf si pour Type1 un déplacement est équivalent à une copie (depuis C++11) ).
Les types Type1 et Type2 doivent être tels qu'un objet de type RandomIt puisse être déréférencé puis implicitement converti vers les deux.

Exigences de type
-
RandomIt doit satisfaire aux exigences de LegacyRandomAccessIterator .
-
Compare doit satisfaire aux exigences de Compare .

Complexité

Étant donné N comme std:: distance ( first, last ) :

1) Au maximum log(N) comparaisons en utilisant operator < (jusqu'à C++20) std:: less { } (depuis C++20) .
2) Au plus log(N) applications de la fonction de comparaison comp .

Exemple

Exécuter ce code 
#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);
}

Sortie : 

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

Rapports de défauts

Les rapports de défauts modifiant le comportement suivants ont été appliqués rétroactivement aux normes C++ précédemment publiées.

DR S'applique à Comportement publié Comportement corrigé
LWG 3032 C++98 les éléments de [ first , last ) n'étaient pas requis d'être interchangeables requis

Voir aussi

(C++11)
vérifie si la plage donnée est un tas maximum
(modèle de fonction)
(C++11)
trouve la plus grande sous-plage qui est un tas maximum
(modèle de fonction)
crée un tas maximum à partir d'une plage d'éléments
(modèle de fonction)
supprime le plus grand élément d'un tas maximum
(modèle de fonction)
transforme un tas maximum en une plage d'éléments triés par ordre croissant
(modèle de fonction)
(C++20)
ajoute un élément à un tas maximum
(objet fonction algorithme)