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

Un tas (de l'anglais heap) en informatique est une structure de données de type arbre qui permet de retrouver directement l'élément que l'on veut traiter en priorité. Pour cela, les clés sont ordonnées selon la propriété de tas : la clé d'un nœud parent a une plus haute priorité que les clés de ses enfants. La "priorité" signifie ici que les clés des enfants sont, soit toutes inférieures, soit toutes supérieures, suivant que le tas est ordonné pour avoir en racine la clé maximale (max heap) ou minimale (min heap).

Une fois traitée, la donnée de plus haute priorité peut ou non être enlevée, ce qui modifie le tas. Un tas est aussi le plus souvent un arbre binaire parfait ou complet avec une hauteur minimale, dans lequel toutes les feuilles sont à la même distance de la racine, plus ou moins 1.

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]

Outre les primitives générales existant sur toute structure de données (taille, création de structure vide, etc.) en définit sur un tas les opérations élémentaires suivantes ; les complexités sont données dans le pire des cas, sans tenir compte de l’amortissement survenant dans les situations réelles.

  • Le tamisage (ou parfois entassement), appliqué à un nœud n dont les fils g et d vérifient tous les deux la condition de tas. Par échange de n avec la racine de l’un des fils g ou d, puis tamisage de celui-ci, le sous-arbre (n, g, d) est transformé en tas. Le coût de l’opération dans le pire des cas est de O(h-p(n)), où p(n) est la profondeur du nœud n et h la hauteur totale du tas.
  • Construction : par tamisages successifs des nœuds de chaque ligne, de la plus grande profondeur à la racine de l’arbre, un arbre parfait quelconque est transformé en arbre. La construction se fait en O(n), où n est le nombre total de nœuds.
  • Ajout d’un élément : l’opération peut être réalisée en O(log(n)), par exemple en insérant le nouvel élément en fin de tas, puis par permutations de sommets deux à deux (équivalentes à des tamisages successifs). Dans certains implémentations, l’insertion est en temps constant mais la propriété de tas n’est pas conservée.
  • Consultation de l’élément de plus grande clef. L’opération est possible en temps constant puisque l’élément de plus grande clef est toujours placé au sommet, faisant de la structure de tas une bonne implémentation des files de priorité.
  • Suppression de l’élément de plus grande clef. De même, l’opération peut conserver la structure de tas avec une complexité de O(log(n)) (en remplaçant l’élément de tête par un élément de priorité minimale située sur la dernière rangée, puis en tamisant au sommet), ou en temps constant sans la contrainte de conserver la structure de tas.
  • Tri par tas : quitte à devoir construire un arbre à partir des données en entrée (en O(n)), il est possible d’extraire le sommet du tas et de tamiser à la racine, en répétant l’opération jusqu’à avoir un tas vide. Les données en entrée sont alors triées dans l’ordre croissant en O(n log(n)) (complexité asymptotique optimale pour un tri) ; et une représentation en mémoire astucieuse (avec des tableaux de taille fixée) permet d’effectuer le tri sur place, c’est-à-dire sans allocation de mémoire supplémentaire autre que la pile d’exécution des récursions. Cependant, ce tri n’est pas stable, et sa complexité temporelle est en pratique inférieure à celle du tri rapide (quicksort).

Certaines implémentations permettent également la suppression d’éléments autres que le sommet, et la modification de la clef d’un élément. Il est possible d’implémenter ces opérations en O(log(n)), mais une structure de données annexe, permettant de retrouver la position d’un élément, doit être gérée pour éviter une recherche dans le tas, non optimisé pour ce genre d’opérations et susceptible de nécessiter O(n) opérations sans cette table annexe.

Voir aussi[modifier | modifier le code]