std::ranges::make_heap
Depuis fr.cppreference.net
| Défini dans l'en-tête <algorithm>
|
||
| Signature d'appel |
||
template< std::random_access_iterator I, std::sentinel_for<I> S,
class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<I, Comp, Proj>
constexpr I make_heap( I first, S last, Comp comp = {}, Proj proj = {} );
|
(1) | (depuis C++20) |
template< ranges::random_access_range R,
class Comp = ranges::less, class Proj = std::identity >
requires std::sortable<ranges::iterator_t<R>, Comp, Proj>
constexpr ranges::borrowed_iterator_t<R>
make_heap( R&& r, Comp comp = {}, Proj proj = {} );
|
(2) | (depuis C++20) |
Construit un tas par rapport à tas par rapport à comp et proj à partir des éléments de la plage spécifiée.
1) La plage spécifiée est
[first, last).2) La plage spécifiée est
r.Les entités de type fonction décrites sur cette page sont des objets fonction d'algorithme (informellement appelés niebloids), c'est-à-dire :
- Les listes d'arguments de modèle explicites ne peuvent pas être spécifiées lors de leur appel.
- Aucune d'entre elles n'est visible par recherche dépendante des arguments.
- Lorsque l'une d'elles est trouvée par recherche non qualifiée normale en tant que nom à gauche de l'opérateur d'appel de fonction, la recherche dépendante des arguments est inhibée.
Paramètres
| first, last | - | la paire itérateur-sentinelle définissant la plage des éléments à modifier |
| r | - |
la
range
des éléments à modifier
|
| comp | - | comparateur à appliquer aux éléments projetés |
| proj | - | projection à appliquer aux éléments |
Valeur de retour
1)
last
2)
ranges::
end
(
r
)
Complexité
Au plus 3·N applications de comp et 6·N applications de proj , où N est :
1)
ranges::
distance
(
first, last
)
2)
ranges::
distance
(
r
)
Exemple
Exécuter ce code
#include <algorithm> #include <cmath> #include <functional> #include <iostream> #include <vector> void out(const auto& what, int n = 1) { while (n-- > 0) std::cout << what; } void print(auto rem, const auto& v) { out(rem); for (auto e : v) out(e), out(' '); out('\n'); } void draw_heap(const auto& v) { auto bails = [](int n, int w) { auto b = [](int w) { out("┌"), out("─", w), out("┴"), out("─", w), out("┐"); }; if (!(n /= 2)) return; for (out(' ', w); n-- > 0;) b(w), out(' ', w + w + 1); out('\n'); }; auto data = [](int n, int w, auto& first, auto last) { for (out(' ', w); n-- > 0 && first != last; ++first) out(*first), out(' ', w + w + 1); out('\n'); }; auto tier = [&](int t, int m, auto& first, auto last) { const int n{1 << t}; const int w{(1 << (m - t - 1)) - 1}; bails(n, w), data(n, w, first, last); }; const int m{static_cast<int>(std::ceil(std::log2(1 + v.size())))}; auto first{v.cbegin()}; for (int i{}; i != m; ++i) tier(i, m, first, v.cend()); } int main() { std::vector h{1, 6, 1, 8, 0, 3, 3, 9, 8, 8, 7, 4, 9, 8, 9}; print("source: ", h); std::ranges::make_heap(h); print("\n" "max-heap: ", h); draw_heap(h); std::ranges::make_heap(h, std::greater{}); print("\n" "min-heap: ", h); draw_heap(h); }
Sortie :
source: 1 6 1 8 0 3 3 9 8 8 7 4 9 8 9
max-heap: 9 8 9 8 8 4 9 6 1 0 7 1 3 8 3
9
┌───┴───┐
8 9
┌─┴─┐ ┌─┴─┐
8 8 4 9
┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐
6 1 0 7 1 3 8 3
min-heap: 0 1 1 8 6 3 3 9 8 8 7 4 9 8 9
0
┌───┴───┐
1 1
┌─┴─┐ ┌─┴─┐
8 6 3 3
┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐
9 8 8 7 4 9 8 9
Voir aussi
(C++20) |
vérifie si la plage donnée est un tas max (objet fonction d'algorithme) |
(C++20) |
trouve la plus grande sous-plage qui est un tas max (objet fonction d'algorithme) |
(C++20) |
ajoute un élément à un tas max (objet fonction d'algorithme) |
(C++20) |
supprime le plus grand élément d'un tas max (objet fonction d'algorithme) |
(C++20) |
transforme un tas max en une plage triée d'éléments (objet fonction d'algorithme) |
| crée un tas max à partir d'une plage d'éléments (modèle de fonction) |