std::push_heap
| 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).
operator<(jusqu'à C++20)std::less{}(depuis C++20).comp.Si l'une des conditions suivantes est satisfaite, le comportement est indéfini :
[first,last - 1)n'est pas un tas selon le comparateur correspondant.
|
(jusqu'à C++11) |
|
(depuis C++11) |
Paramètres
| first, last | - | la paire d'itérateurs définissant la plage d'éléments qui forment le tas binaire après l'insertion |
| comp | - | objet fonction de comparaison (c'est-à-dire un objet qui satisfait les 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 :
Bien que la signature n'ait pas besoin d'avoir |
| Exigences de type | ||
-RandomIt doit satisfaire les exigences de LegacyRandomAccessIterator. | ||
-Compare doit satisfaire les exigences de Compare. | ||
Complexité
Étant donné N comme std::distance(first, last):
operator<(jusqu'à C++20)std::less{}(depuis C++20).comp.Exemple
#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 | Appliqué à | Comportement tel que publié | Comportement correct |
|---|---|---|---|
| LWG 3032 | C++98 | les éléments de [first, last) ne devait pas être échangeable |
requis |
Voir aussi
(C++11) |
vérifie si la plage donnée est un tas max (modèle de fonction & objet fonction d'algorithme) |
(C++20) |
|
(C++11) |
trouve la plus grande sous-plage qui est un tas max (modèle de fonction & objet fonction d'algorithme) |
(C++20) |
|
| crée un tas max à partir d'une plage d'éléments (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| supprime le plus grand élément d'un tas max (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
| transforme un tas max en une plage d'éléments triés par ordre croissant (modèle de fonction & objet fonction d'algorithme) | |
(C++20) |
|
(C++20) |
ajoute un élément à un tas max (objet fonction d'algorithme) |