Tas (informatique)

vignette|Un exemple de tas. Il contient 9 éléments. L'élément le plus prioritaire (100) est à la racine. En informatique, un tas (ou monceau au Canada, heap en anglais) est une structure de données de type arbre qui permet de retrouver directement l'élément que l'on veut traiter en priorité. C'est un arbre binaire presque complet ordonné. Un arbre binaire est dit presque complet si tous ses niveaux sont remplis, sauf éventuellement le dernier, qui doit être rempli sur la gauche (cf. Contre-exemples). Ses feuilles sont donc à la même distance minimale de la racine, plus ou moins 1. Pour utiliser un tas, 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. Les tas ont été introduits par en 1964 pour l'algorithme du tri par tas (cf la section ci-après pour une première introduction à ce tri). On dit qu'un arbre est ordonné en tas lorsque la propriété suivante est vérifiée : ou 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 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. On peut ainsi représenter un tas à n éléments par un tableau à n cases, de la façon suivante : Si on note 0 le numéro de la racine du tas, on peut définir récursivement le numéro de tous les sommets dans l'arbre, grâce à la formule : pour un sommet parent numéroté i, son fils gauche aura pour numéro 2i+1, et son fils droit 2i+2.