Utiliser les algorithmes de tas STL en C++

Utilisez les algorithmes de tas de la STL C++ pour transformer une plage de std::vector en tas max, trier cette plage ou déplacer sa plus grande valeur à la fin. std::pop_heap déplace la valeur ; appelez séparément une fonction d’effacement si vous voulez la retirer du vecteur.

Utiliser la fonction std::make_heap pour transformer une plage en tas

Un tas est une plage organisée de façon à respecter une relation entre parents et enfants. Avec le comparateur par défaut, std::make_heap construit un tas max : chaque parent est supérieur ou égal à ses enfants, de sorte que la plus grande valeur se trouve au début. Dans un tas binaire stocké dans un vecteur, les enfants de l’élément d’indice i se trouvent aux indices 2 * i + 1 et 2 * i + 2, si ces positions appartiennent à la plage. Un tas min utilise un autre comparateur, par exemple std::greater<int>.

std::make_heap réorganise les éléments pour respecter la propriété de tas ; la fonction ne trie pas toute la plage. Plusieurs dispositions peuvent respecter cette même propriété. Le code doit donc s’appuyer sur la valeur au début et sur les comparaisons entre parents et enfants, plutôt que sur une séquence particulière après l’appel.

L’exemple autonome suivant construit un tas et vérifie la relation entre parents et enfants. Son exécution a réussi. Les libellés de la sortie ci-dessous restent en anglais : elle indique que la vérification du tas max vaut true et que la valeur au sommet est 91.

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{11, 82, 39, 72, 51, 32, 91};
    std::make_heap(values.begin(), values.end());

    bool is_max_heap = true;
    for (std::size_t child = 1; child < values.size(); ++child) {
        const std::size_t parent = (child - 1) / 2;
        if (values[parent] < values[child]) {
            is_max_heap = false;
            break;
        }
    }

    std::cout << "max-heap: " << std::boolalpha << is_max_heap << '\n';
    std::cout << "top: " << values.front() << '\n';
}

max-heap: true
top: 91

Le premier élément est la valeur au sommet du tas. L’ordre des autres éléments du vecteur est uniquement limité par la propriété de tas ; il ne faut donc pas le considérer comme une liste croissante ou décroissante.

Utiliser la fonction std::sort_heap pour trier une plage de tas

Appelez std::sort_heap sur une plage qui respecte déjà la propriété de tas. Avec le comparateur par défaut, la fonction réorganise la plage dans l’ordre croissant. Après le tri, la plage ne respecte plus la propriété de tas : appelez donc à nouveau std::make_heap avant d’utiliser un algorithme de tas sur toute la plage.

Par exemple, après std::make_heap(values.begin(), values.end()), appelez std::sort_heap(values.begin(), values.end()) pour trier cette même plage. Le comparateur par défaut produit un ordre croissant.

La surcharge qui prend un comparateur accepte une fonction ou un objet fonction qui définit l’ordre. Utilisez le même comparateur pour construire et trier un tas ; par exemple, un tas construit avec std::greater<int> doit être trié avec ce comparateur. La surcharge par défaut convient lorsque le résultat souhaité est un ordre croissant.

Utiliser la fonction std::pop_heap pour déplacer l’élément suivant du tas

std::pop_heap déplace la valeur au sommet vers la dernière position de la plage et rétablit la propriété de tas dans la plage qui la précède. La taille du vecteur ne change pas. Pour retirer cette valeur du conteneur, appelez pop_back() après std::pop_heap.

Pour ajouter un élément, ajoutez-le au vecteur, puis appelez std::push_heap. La plage précédant l’élément ajouté doit déjà former un tas ; std::push_heap rétablit ensuite la propriété de tas sur la plage agrandie. Utilisez le même comparateur que celui qui définit le tas pour ces deux algorithmes.

Cet exemple autonome vérifie la valeur déplacée au sommet, l’efface séparément, puis ajoute une valeur tout en maintenant le tas. Son exécution a réussi. Les libellés de la sortie ci-dessous restent en anglais : elle indique que la valeur déplacée est 91 et que la nouvelle valeur au sommet est 95.

#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> values{11, 82, 39, 72, 51, 32, 91};
    std::make_heap(values.begin(), values.end());

    std::pop_heap(values.begin(), values.end());
    std::cout << "moved top: " << values.back() << '\n';
    values.pop_back();

    values.push_back(95);
    std::push_heap(values.begin(), values.end());
    std::cout << "new top: " << values.front() << '\n';
}

moved top: 91
new top: 95

Après std::pop_heap, le préfixe qui s’arrête avant le dernier élément est le tas à réutiliser. Une fois que pop_back() a retiré la dernière valeur, le vecteur contient de nouveau exactement cette plage de tas. Si vous ajoutez un élément sans préserver d’abord cet invariant, vous ne respectez pas la précondition de std::push_heap.