Utiliser les algorithmes de tas STL en C++

1. Utilisez la fonction std::make_heap pour convertir une plage en un tas
2. Utilisez la fonction std::sort_heap pour trier une plage de tas
3. Utilisez la fonction std::pop_heap pour supprimer l’élément suivant du tas

Cet article montrera comment utiliser les algorithmes de tas STL en C++.

Utilisez la fonction std::make_heap pour convertir une plage en un tas

La fonction std::make_heap est fournie sous les algorithmes STL, et elle peut être utilisée pour construire une structure de données de tas binaire à partir de la plage donnée. Généralement, une structure de données de tas est basée sur une arborescence et les deux types courants sont appelés tas max et tas min.

Dans un tas max, pour tout nœud enfant, la clé de son nœud parent est supérieure ou égale à la clé de l’enfant. D’autre part, la clé du parent est inférieure à la clé de l’enfant. Maintenant, la structure de tas construite avec la fonction make_heap est un tas binaire similaire à une structure de données d’arbre binaire. Notez que les tas sont efficaces pour les opérations d’insertion et de suppression d’éléments, qui peuvent être effectuées en temps logarithmique.

L’exemple suivant montre la transformation du processus std::vector en un tas, puis le contenu est imprimé à l’aide de la fonction habituelle printVector. Notez que l’ordre des éléments est légèrement mystérieux. En fait, vous pouvez les lire comme l’arborescence binaire où le premier élément est la valeur de la clé racine.

Comme il n’y a que deux enfants au maximum pour chaque nœud dans un arbre binaire, les 82 et 39 suivent la racine en tant qu’enfants. Les deux éléments suivants sont les nœuds enfants de 82, et les deux autres sont positionnés sous 39. Cette hiérarchie satisfait à la propriété max heap selon laquelle l’élément parent a la clé supérieure ou égale à celle de ses enfants.

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

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

int main() {
  vector<int> vec1{11, 82, 39, 72, 51, 32, 91};
  cout << "vec1 original:  ";
  printVector(vec1);

  std::make_heap(vec1.begin(), vec1.end());
  cout << "vec1 make_heap: ";
  printVector(vec1);

  return EXIT_SUCCESS;
}

Production:

vec1 original : 11;
82;
39;
72;
51;
32;
91;
vec1 make_heap : 91;
82;
39;
72;
51;
32;
11;

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

Vous pouvez utiliser la fonction std::sort_heap pour trier la plage précédemment convertie à l’aide de la fonction std::make_heap. La simple surcharge de la fonction std::sort_heap, qui ne prend que deux arguments d’itérateur, va trier les rangs par ordre croissant. L’autre surcharge de la fonction peut accepter le troisième argument de la fonction de comparaison avec la signature suivante : bool cmp(const Type1 &a, const Type2 &b);. Une fois la plage triée, elle n’a plus la propriété de tas.

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

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

int main() {
  vector<int> vec1{11, 82, 39, 72, 51, 32, 91};

  std::make_heap(vec1.begin(), vec1.end());
  printVector(vec1);

  std::sort_heap(vec1.begin(), vec1.end());
  printVector(vec1);

  return EXIT_SUCCESS;
}

Production:

91;
82;
39;
72;
51;
32;
11;
11;
32;
39;
51;
72;
82;
91;

Utilisez la fonction std::pop_heap pour supprimer l’élément suivant du tas

Les structures de tas prennent généralement en charge les opérations d’insertion et de retrait d’éléments rapides. Les fonctions std::push_heap et std::pop_heap effectuent ces opérations pour la plage de tas en conséquence. Lorsque la commande std::push_heap est appelée sur la plage de tas, son premier élément est échangé avec la dernière position et un nouveau tas est construit avec les éléments restants. Notez que le tas est construit comme un tas max par les paramètres par défaut. On peut passer une fonction de comparaison facultative comme troisième argument pour modifier la hiérarchie du tas en conséquence.

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

using std::cout;
using std::endl;
using std::string;
using std::vector;

template <typename T>
void printVector(const vector<T> &vec) {
  for (auto &i : vec) {
    cout << i << "; ";
  }
  cout << endl;
}

int main() {
  vector<int> vec1{11, 82, 39, 72, 51, 32, 91};

  std::make_heap(vec1.begin(), vec1.end());
  printVector(vec1);

  std::pop_heap(vec1.begin(), vec1.end());
  printVector(vec1);

  return EXIT_SUCCESS;
}

Production:

91;
82;
39;
72;
51;
32;
11;
82;
72;
39;
11;
51;
32;
91;