Aller au contenu

TNSI : Tas Binaires⚓︎

Def

  • Un Tas Binaire (à gauche) 🇫🇷 ou heap 🇬🇧 est un arbre binaire complet (à gauche), tel que :
    • Ordre du Tas : le noeud racine porte une donnée plus grande à celle de tous les autres noeuds, et tels que
    • ses deux sous-arbres soient aussi des tas
      Cet arbre est appelé un Tas-max 🇫🇷 ou max-heap 🇬🇧
  • Un Tas-min 🇫🇷 ou min-heap 🇬🇧 a la même structure, mais chaque noeud porte une information plus petite que tous ses descendants.

Cas de Figure sur les Tas Binaire⚓︎

Tas Binaire de type Tas-max⚓︎

TAS55335--3225--2
Tas Binaire
(Tas-max)
TAS99559--5779--7445--4115--1
Tas Binaire
(Tas-max)
TAS10108810--86610--6338--3778--7226--2v16--v1v2
Tas Binaire
(Tas-max)
TAS5050393950--39464650--46v139--v1171739--17131339--13111146--11252546--25v246--v2121217--12151517--15
Tas Binaire (Tas-max)
TAS1001008282100--825656100--56v182--v14014082--401626282--62383856--38272756--27v256--v23535401--352424401--24545462--544024062--402232335--23282835--28202024--20161624--16222238--22303038--30141427--14151527--15464654--46v354--v3
Tas Binaire (Tas-max)

Tas Binaire de type Tas-min⚓︎

TAS22662--6882--8
Tas Binaire
(Tas-min)
TAS33993--9443--412129--12v19--v1
Tas Binaire
(Tas-min)
TAS11441--4771--7101104--101884--8102107--102v17--v1v2
Tas Binaire
(Tas-min)
TAS44884--8554--5v18--v110108--1014148--1412125--1230305--30v25--v2161610--16252510--25202014--20181814--18151512--15v312--v3
Tas Binaire (Tas-min)
TAS7712127--1217177--17v112--v1252512--25202012--20383817--38272717--27v217--v2262625--26313125--31343420--345015020--501292926--29434326--435025031--502363631--36424238--42404038--405035027--503545427--54464634--46414134--415252501--525656501--56454542--45v342--v3
Tas Binaire (Tas-min)

PAS un Tas Binaire. Justifiez⚓︎

TAS55335--3665--6v13--v1113--1
Pas un
Tas Binaire
TAS88228--2998--9442--4332--3
Pas un
Tas Binaire
TAS10108810--87710--7998--9668--6v17--v1227--2v2
Pas un
Tas Binaire
TAS4040363640--36434340--43v136--v1242436--24131336--13111143--11252543--25v243--v2202024--20181824--188811--8101011--10
Pas un Tas Binaire
TAS9090858590--85636390--63v185--v14014085--401626285--62494963--49212163--21v263--v23535401--352424401--24545462--544024062--402232335--23363635--36202024--20v424--v4222249--22343449--34181821--186621--6484854--48424254--42v3
Pas un Tas Binaire

Implémentations des Tas Binaires⚓︎

  • Files de Priorité : Les Tas Binaires de type tas-max (resp. tas-min) sont efficaces pour déterminer rapidement la plus grande valeur, donc le max (resp. la plus petite valeur, donc le min) dans une structure de données sous forme d'arbre binaire. C'est leur utilité principale. Les Tas Binaires sont donc utiles pour implémenter le type abstrait de données (TAD) appelé des Files de Priorité
  • Tri par Tas : Les Tas Binaires de type tas-max (resp. tas-min) sont utilisés pour un algorithme de tri ("par tas") efficace ascendant (resp. descendant)

Limitations des Tas Binaires⚓︎

Un Tas Binaire n'est pas adapté aux Opérations suivantes d'un Arbre :

  • Recherche d'un élément quelconque
  • Insertion d'un élément quelconque
  • Suppression d'un élément quelconque

En effet, la Complexité de chacune des opérations précédentes est en \(O(n)\), donc lent. Pour ce type d'utilisation, on préférera les Arbres Binaires de Recherche (ABR), qui sont bien plus adaptés.