Namespaces
Variants

std:: make_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 make_heap ( RandomIt first, RandomIt last ) ;
(1) (constexpr depuis C++20)
template < class RandomIt, class Compare >
void make_heap ( RandomIt first, RandomIt last, Compare comp ) ;
(2) (constexpr depuis C++20)

Construit un tas dans l'intervalle [ first , last ) .

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

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

(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 pour créer la plage de tas binaire
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é , ni 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 3N comparaisons en utilisant operator < (jusqu'à C++20) std:: less { } (depuis C++20) .
2) Au plus 3N applications de la fonction de comparaison comp .

Exemple

Exécuter ce code 
#include <algorithm>
#include <functional>
#include <iostream>
#include <string_view>
#include <vector>
void print(std::string_view text, const std::vector<int>& v = {})
{
    std::cout << text << ": ";
    for (const auto& e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}
int main()
{
    print("Max heap");
    std::vector<int> v{3, 2, 4, 1, 5, 9};
    print("initially, v", v);
    std::make_heap(v.begin(), v.end());
    print("after make_heap, v", v);
    std::pop_heap(v.begin(), v.end());
    print("after pop_heap, v", v);
    auto top = v.back();
    v.pop_back();
    print("former top element", {top});
    print("after removing the former top element, v", v);
    print("\nMin heap");
    std::vector<int> v1{3, 2, 4, 1, 5, 9};
    print("initially, v1", v1);
    std::make_heap(v1.begin(), v1.end(), std::greater<>{});
    print("after make_heap, v1", v1);
    std::pop_heap(v1.begin(), v1.end(), std::greater<>{});
    print("after pop_heap, v1", v1);
    auto top1 = v1.back();
    v1.pop_back();
    print("former top element", {top1});
    print("after removing the former top element, v1", v1);
}

Sortie : 

Max heap:
initially, v: 3 2 4 1 5 9
after make_heap, v: 9 5 4 1 2 3
after pop_heap, v: 5 3 4 1 2 9
former top element: 9
after removing the former top element, v: 5 3 4 1 2
Min heap:
initially, v1: 3 2 4 1 5 9
after make_heap, v1: 1 2 4 3 5 9
after pop_heap, v1: 2 3 4 9 5 1
former top element: 1
after removing the former top element, v1: 2 3 4 9 5

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 Applicable à Comportement publié Comportement correct
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)
ajoute un élément à un tas maximum
(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)
adapte un conteneur pour fournir une file de priorité
(modèle de classe)
(C++20)
crée un tas maximum à partir d'une plage d'éléments
(objet fonction algorithme)