Tas (heap) en C++

La standard template library (STL) fournit les fonctionalités d'un tas via un ensemble de fonctions de la librairie <algorithm>

Fonction Description
std::push_heap ajoute un élément dans un tas
std::pop_heap supprime l'élément au sommet d'un tas
std::make_heap crée un tas à partir d'un tableau quelconque
std::sort_heap trie les éléments à partir d'un tas
std::is_heap vérifie si les éléments respectent la condition de tas
std::is_heap_until trouve le premier élément ne respectant pas la condition de tas

Ces fonctions ont toutes le même prototype.

Soit la version générale

In [1]:
template <class RandomAccessIterator, class Compare>
void xxx_heap (RandomAccessIterator first, 
               RandomAccessIterator last,
               Compare comp);

qui prend en entrée

  • une séquence d'éléments dans l'intervalle [first,last[
  • une fonction de comparaison de type
In [2]:
template <typename T> 
bool comp(const T& a, const T& b) {
    return a < b; 
}

Soit la version simple

In [3]:
template <class RandomAccessIterator>
void xxx_heap (RandomAccessIterator first, 
               RandomAccessIterator last);

qui utilise T::operator<(const T&) pour comparer des éléments de type T.

La fonction is_heap retourne évidemment un bool,

et is_heap_until retourne un itérateur.

En pratique...

L'interface basé sur des itérateurs a comme conséquence que

  • les fonctions n'ont pas accès aux conteneurs
  • elles ne peuvent pas ajouter au supprimer d'éléments
  • elles ne peuvent que ré-ordonner les éléments

Observons leurs effets

In [5]:
// Créer le tas 

std::vector<int> v { 1, 2, 3, 4, 5, 6, 7, 8 };
std::make_heap(v.begin(),v.end());
v
Out[5]:
{ 8, 5, 7, 4, 1, 6, 3, 2 }
In [6]:
// Ajouter l'élément 9 au vecteur

v.push_back(9);
v
Out[6]:
{ 8, 5, 7, 4, 1, 6, 3, 2, 9 }
In [7]:
// Placer le dernier élément dans le tas 

std::push_heap(v.begin(),v.end());
v
Out[7]:
{ 9, 8, 7, 5, 1, 6, 3, 2, 4 }
In [8]:
// Placer le sommet en queue du tas et rétablir le tas pour les autres éléments

std::pop_heap(v.begin(),v.end());
v
Out[8]:
{ 8, 5, 7, 4, 1, 6, 3, 2, 9 }
In [9]:
// supprimer le dernier élément 

v.pop_back();
v
Out[9]:
{ 8, 5, 7, 4, 1, 6, 3, 2 }
In [10]:
// Trier à partir du tas v

std::sort_heap(v.begin(),v.end());
v
Out[10]:
{ 1, 2, 3, 4, 5, 6, 7, 8 }
In [11]:
// vérifier si c'est un tas 

std::cout << std::is_heap(v.begin(),v.end());

false
In [12]:
// Trouver le premier élément plus grand que son parent 

std::cout << *(std::is_heap_until(v.begin(),v.end()));

2

Attention

Pour que ces fonctions s'exécutent correctement, il est essentiel que les pré-conditions soient respectées.

Fonctions Pré-condition
std::pop_heap(first,last)
std::sort_heap(first,last)		 [first,last[ respecte la condition de tas
std::push_heap(first,last) [first,last-1[ respecte la condition de tas

Sinon, l'algorithme est appliqué

  • montée dans un tas (push_heap)
  • échange(s) et descente(s) dans un tas (pop_heap et sort_heap)

mais le résultat final n'est pas nécessairement

  • un tas (push_heap et pop_heap)
  • trié (sort_heap)
In [13]:
// ajout dans un tas incorrect

v.assign({ 1, 2, 3, 4, 5, 6, 7 });
std::push_heap(v.begin(),v.end());
std::cout << std::is_heap(v.begin(),v.end());
v

false
Out[13]:
{ 7, 2, 1, 4, 5, 6, 3 }
In [14]:
// suppression d'un tas incorrect

v.assign({ 1, 2, 3, 4, 5, 6, 7 });
std::pop_heap(v.begin(),v.end());
std::cout << std::is_heap(v.begin(),v.end()-1);
v

false
Out[14]:
{ 7, 2, 3, 4, 5, 6, 1 }
In [15]:
// tri à partir d'une séquence pas en tas 

v.assign({ 1, 2, 3, 4, 5, 6, 7 });
std::sort_heap(v.begin(),v.end());
v
Out[15]:
{ 2, 3, 4, 5, 6, 7, 1 }

ASD1 Notebooks on GitHub.io

© Olivier Cuisenaire, 2018