Tas (informatique)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Tas.
Un exemple de tas

En informatique, un tas, en anglais heap, est une structure de données qui peut être représentée par un arbre complet à gauche et qui vérifie la condition d'ordre d'un tas : la clé d'un nœud est supérieur ou égale à la clé de chacun de ses fils.

Description[modifier | modifier le code]

On dit qu'un arbre est ordonné en tas lorsque la propriété suivante est vérifiée :

Pour tous nœuds A et B de l'arbre tels que B soit un fils de A
clé(A) ≥ clé(B)

ou

Pour tous nœuds A et B de l'arbre tels que B soit un fils de A
clé(A) ≤ clé(B)

Un arbre vérifiant cette propriété est aussi appelé "arbre tournoi". Cette propriété implique que la plus grande clé (ou la plus petite) soit située à la racine du tas. Ils sont ainsi très utilisés pour implémenter les files à priorités car ils permettent des insertions en temps logarithmique et un accès direct au plus grand élément. L'efficacité des opérations effectuée sur des tas est très importante dans de nombreux algorithmes sur les graphes. Les tas sont en outre utilisés dans l'algorithme de tri par tas.

Remarques[modifier | modifier le code]

  • La notion de plus grande clé est équivalente à la notion de plus petite clé, seule diffère la relation d'ordre total utilisée. Les algorithmes restent donc les mêmes si l'on veut accéder directement au plus petit élément et non au plus grand. On peut même, dans la plupart des langages de programmation modernes, programmer de façon à passer la relation d'ordre désirée en paramètre des algorithmes de construction et de manipulation de tas.

Attention : un tas est organisé selon une seule relation d'ordre à la fois. Il faut donc décider dès sa construction si l'on veut accéder ensuite au plus grand élément, ou au plus petit, et selon quel attribut de l'objet stocké dans l'étiquette de chaque nœud. Les manipulations suivantes de ce tas devront obligatoirement se faire par rapport à la même relation d'ordre.

Contre-exemples[modifier | modifier le code]

Les deux contre-exemples suivants ont pour relation d'ordre : valeur(\mathrm{p\grave{e}re}) \ge valeur(fils)

Contre-exemple n°1
Contre-exemple n°2

Primitives[modifier | modifier le code]

Les Tas supportent les opérations suivantes :

  • Construire-Tas
  • Ajouter-Élément
  • Consulter-Sommet
  • Retirer-Élément
  • Tamiser (refabriquer le tas pour qu'il retrouve ses propriétés; par exemple suite à l'ajout ou la suppression d'un élément)
  • Tri-Par-Tas

Selon les implémentations, les primitives Ajouter-Élément et Retirer-Élément invalident la propriété de Tas, ou bien appellent la procédure Tamiser pour le réorganiser.

Souvent Retirer-Élément n'est appelée que pour retirer le sommet.

Voir aussi[modifier | modifier le code]