Tas (informatique)
En informatique, un tas[1] (ou monceau au Canada[2], 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) en 1964 pour l'algorithme du tri par tas (cf la section ci-aprÚs pour une premiÚre introduction à ce tri)[3].
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 »[4]. 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.
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. Le parent d'un sommet j a donc toujours pour numéro la partie entiÚre inférieure de (j-1)/2.
Remarques
- 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
Les deux contre-exemples suivants ont pour relation d'ordre :
Contre-exemple no 1 |
Contre-exemple no 2 |
Primitives
Outre les primitives gĂ©nĂ©rales existant sur toute structure de donnĂ©es (taille, crĂ©ation de structure vide, etc.), on 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. Dans toute la suite, on considĂšre qu'un tas est implĂ©mentĂ© comme un tableau, comme expliquĂ© dans la dĂ©finition, et on considĂšre que c'est la plus grande clĂ© qui est Ă la racine. (les implĂ©mentations sont en Pseudo-code puis Python, on note T le tas, i reprĂ©sente un indice et e un Ă©lĂ©ment) :
Enfiler
Pour enfiler un élément, on le place comme feuille, puis on fait "remonter" l'élément pour maintenir la priorité du tas.
Pseudo-code :
Fonction enfiler (T,e) ajouter e Ă T en derniĂšre position T.taille=T.taille+1 appeler tasser_1 (T,T.taille) retourner T
Python :
def enfiler(T, e):
"""On ajoute une feuille au tas, et on la tasse"""
T = T + [e]
tasser_1(T, len(T) - 1)
return T
La fonction tasser_1
prend en entrée un arbre binaire presque complet, tel que celui-ci est un tas, sauf éventuellement au niveau de T[i], et retourne l'arbre réordonné en tas. Pour cela, il compare T[i] à son parent, on les échange si T[i] est plus grand que son parent, et on recommence, ou alors on stoppe l'algorithme :
Pseudo-code :
Fonction tasser_1 (T,i) k = si k = Ă©changer et appeler tasser_1 (T,)
Python :
import numpy as np
def tasser_1(T, index):
"""On tasse des feuilles vers la racine"""
# a//b correspond au quotient de a par b
index_parent = (index - 1) // 2
# np.argmax permet de renvoyer la place du plus grand élément d'un tableau donné
# ex: np.argmax([3,1,2]) renvoie 0
k = np.argmax([T[index], T[index_parent]])
if k == 0:
# Echange des deux noeuds: a,b = b,a
T[index], T[index_parent] = T[index_parent], T[index]
# Si le noeud parent n'est pas la racine
# on continue de tasser Ă partir de l'index parent
if index_parent != 0:
tasser_1(T, index_parent)
LâopĂ©ration peut ĂȘtre rĂ©alisĂ©e en O(log(n)). Dans certaines implĂ©mentations, lâinsertion est en temps constant mais la propriĂ©tĂ© de tas nâest pas conservĂ©e.
DĂ©filer
Quand on dĂ©file un Ă©lĂ©ment d'un tas, c'est toujours celui de prioritĂ© maximale. Il correspond donc Ă la racine du tas. LâopĂ©ration peut conserver la structure de tas avec une complexitĂ© de O(log(n)) ; en effet, il ne reste alors qu'Ă rĂ©ordonner l'arbre privĂ© de sa racine pour en faire un nouveau tas, en plaçant la derniĂšre feuille Ă la racine, puis par tamisage successif (on peut Ă©galement seulement lire l'Ă©lĂ©ment, sans pour autant le supprimer du tas, en temps constant) :
Pseudo-code :
Fonction défiler (T) m:=T[1] T[1]:=T[T.taille] T.taille=T.taille-1 appeler tasser (T,1) retourner m
Python :
def defiler(T):
m = T[0]
T[0] = T[-1] # T[-1] correspond au derner élément de T
T = T[:-1] # T[:-1] correspond au tableau T sans le dernier élément
tasser(T, 0)
return m
La fonction tasser
prend en entrée un arbre binaire presque complet, tel que T est un tas sauf éventuellement en T[i], et retourne l'arbre réordonné en un tas.
Pseudo-code :
Fonction tasser (T,i) k= si ki Ă©changer et appeler tasser (T,k)
Python :
import numpy as np
def tasser(T, index):
"""On tasse de la racine vers les feuilles"""
index_fils_gauche = index * 2 + 1
index_fils_droit = index * 2 + 2
# Verification de la présence d'un fils droit
if index_fils_droit < len(T):
A = [T[index], T[index_fils_gauche], T[index_fils_droit]]
else:
A = [T[index], T[index_fils_gauche]]
# L'ordre de A permet d'obtenir un décalage (0, 1 ou 2)
decalage = np.argmax(A)
# Si le décalage vaut 0, le noeud courant est à sa place
# donc on arrĂȘte de tasser
if decalage != 0:
# Sinon un des fils est plus grand, donc on l'Ă©change de place
index_plus_grand_fils = index * 2 + decalage
T[index], T[index_plus_grand_fils] = T[index_plus_grand_fils], T[index]
nouvel_index = index_plus_grand_fils
# Si le noeud a encore des fils, on continue de tasser
index_nouveau_fils_gauche = 2 * (nouvel_index) + 1
if index_nouveau_fils_gauche < len(T):
tasser(T, nouvel_index)
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 permet, par Ă©change de n avec lâun des fils g ou d, puis tamisage du sous arbre reprĂ©sentĂ© par le fils Ă©changĂ©, de transformer le sous arbre (n, g, d) 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 (cette hauteur Ă©tant en logarithme du nombre de nĆud, car on a affaire a un arbre presque complet).
Construction
Pour construire un tas à partir d'un arbre (implémenté comme un tableau), il suffit de le tasser successivement, en partant "en bas" de l'arbre, sans se préoccuper des feuilles :
Pseudo-code :
Fonction construire_tas (T) T.taille= pour i allant de Ă 1 appeler tasser (T,i)
Python :
def construire_tas(T):
for i in range(len(T) // 2, 0, -1):
tasser(T, i)
La construction se fait en O(n), oĂč n est le nombre total de nĆuds.
Applications
La structure de tas possĂšde possĂšde de nombreuses applications pratiques, parmi lesquelles :
- Le tri par tas : un algorithme de tri qui peut ĂȘtre implĂ©mentĂ© sur place avec une complexitĂ© asymptotique moyenne et dans le pire des cas linĂ©arithmique, O(n ln n).
- En plus de permettre l'accÚs au plus petit ou plus grand élément, le tas permet aussi l'accÚs à d'autres éléments spécifiques tels que le médian ou le k-iÚme élément en un temps sous-linéaire en le nombre d'éléments du tas.
- La structure de tas est exploitée par divers algorithmes de parcours de graphes, tels que l'algorithme de Dijkstra ou la recherche d'un arbre couvrant minimal de Prim.
- Le tas se prĂȘte particuliĂšrement Ă l'implĂ©mentation d'une file de prioritĂ©, en plaçant l'Ă©lĂ©ment de plus forte prioritĂ© Ă sa racine.
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.
Implémentations
- La bibliothĂšque standard du C++ propose les primitives
make_heap
,push_heap
etpop_heap
qui permettent la création de tas, l'insertion et l'extraction d'un élément respectivement. Les tas sont représentés en machine par des tableaux et la méthodepriority_queue
permet l'utilisation directe de la structure dans une file de priorité. En revanche, le catalogue ne permet pas de tamiser un élément ou d'en modifier la clé directement. - La bibliothÚque boost de C++ étend l'implémentation des tas en permettant de modifier les clés et en introduisant les tas d-aires, binomiaux, les tas de Fibonacci et d'appariement.
- Java offre depuis sa version 1.5 une implémentation des tas binaires avec la classe
java.util.PriorityQueue
. Seuls les tas-min sont disponibles nativement, pour avoir un tas-max, l'utilisateur devra définir son propre comparateur. Il n'est pas possible de tamiser un élément ou d'en modifier la clé directement. - Pour Python, le module
heapq
implémente une file de priorité par un tas binaire. - PHP propose à la fois le tas-min (
SplMinHeap
) et le tas-max (SplMaxHeap
) dans sa bibliothÚque standard en version 5.3. - Perl apporte une implémentation de tas binaires, binomiaux et de Fibonacci avec la distribution Heap disponible depuis CPAN.
- Pour Pharo, une implémentation est disponible dans le module
Collections-Sequenceable
, qui contient aussi un catalogue d'exemples. - Le langage Rust a une implémentation tas-max,
BinaryHeap
est accessible depuis le modulecollections
de sa bibliothĂšque standard.
Références
- (en) Thomas H. Cormen, Introduction to Algorithms, 1313 p. (lire en ligne), p. 151-169
- Robert LaganiÚre, « CSI 2510 : Structure de données et algorithmes », sur site.uottawa.ca (consulté le )
- JWJ Williams, « Algorithm 232: Heapsort », Communication of the ACM, vol. 7,â , p. 347â348 (lire en ligne, consultĂ© le )
- Judicaël Courant, Arbres tournois, tas-max, , 7 p. (lire en ligne)