meule - puzzles en ligne
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 J. W. J. Williams en 1964 pour l' algorithme du tri par tas (cf la section ci-après pour une première introduction à ce tri).
Description
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 ».
