Tas (informatique)

Tas (informatique)
Page d'aide sur l'homonymie Pour les articles homonymes, voir Tas.
Un exemple de tas

En informatique, un tas, en anglais heap, (ou plus précisément un tas binaire) est une structure de données répondant aux conditions suivantes :

Sommaire

Description

On dit qu'un arbre est ordonné en tas lorsque la propriété suivante est vérifiée : les nœuds sont ordonnés par leurs clés respectives, et :

Pour tout nœuds A et B de l'arbre tels que B soit un fils de A 
   clé(A) ≥ clé(B)

ou

Pour tout 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.

Le fait qu'un tas soit un arbre binaire complet permet de le représenter d'une manière intuitive par un tableau unidimensionnel.

  • Tableau indicé à partir de 0 : le père d'un nœud en position i a pour position \lfloor (i-1)/2 \rfloor, et donc les enfants d'un nœud en position i sont situés à 2i+1 et 2i+2.
  • Tableau indicé à partir de 1 : le père d'un nœud en position i a pour position \lfloor i/2 \rfloor, et donc les enfants d'un nœud en position i sont situés à 2i et 2i+1.

Les tas sont en outre utilisés dans l'algorithme de tri par tas.

Remarques

  • Les multiples définitions existantes pour « arbre complet » peuvent porter à confusion. Ici, il est important que les nœuds de l'arbre puissent être stockés de façon contiguë dans un tableau. Donc, tous les étages, de la racine jusqu'à l'avant-dernier, doivent obligatoirement être remplis. De plus, les feuilles de la dernière ligne doivent être "calées à gauche". En revanche, un tas pouvant avoir un nombre quelconque d'éléments, il n'est pas obligatoire que la dernière ligne soit complètement remplie.
  • 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 : valeur(\mathrm{p\grave{e}re}) \ge valeur(fils)

Contre-exemple n°1
Contre-exemple n°2

Primitives

Les Tas supportent les opérations suivantes :

  • Construire-Tas
  • Ajouter-Élément
  • Consulter-Sommet
  • Retirer-Élément
  • Tamiser
  • Tri-Par-Tas

Selon les implémentations, les primitives Ajouter-Élément et Retirer-Élément invalident la propriété de Tas, ou bien appellent la procédure Tamiser pour le réorganiser.

Souvent Retirer-Élément n'est appelée que pour retirer le sommet.

Voir aussi

Articles connexes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Tas (informatique) de Wikipédia en français (auteurs)

Игры ⚽ Нужно решить контрольную?

Regardez d'autres dictionnaires:

  • Tas (mathématique) — Tas (informatique) Pour les articles homonymes, voir Tas. Un exemple de tas En informatique, un tas, en anglais …   Wikipédia en Français

  • Tas binaire — Tas (informatique) Pour les articles homonymes, voir Tas. Un exemple de tas En informatique, un tas, en anglais …   Wikipédia en Français

  • Informatique Théorique — L informatique théorique est l étude des fondements logiques et mathématiques de l informatique. Plus généralement, le terme est utilisé pour désigner des domaines ou sous domaines de recherche centrés sur des vérités universelles (axiomes) en… …   Wikipédia en Français

  • Informatique theorique — Informatique théorique L informatique théorique est l étude des fondements logiques et mathématiques de l informatique. Plus généralement, le terme est utilisé pour désigner des domaines ou sous domaines de recherche centrés sur des vérités… …   Wikipédia en Français

  • Informatique théorique — L informatique théorique est l étude des fondements logiques et mathématiques de l informatique. Plus généralement, le terme est utilisé pour désigner des domaines ou sous domaines de recherche centrés sur des vérités universelles (axiomes) en… …   Wikipédia en Français

  • Tas de fibonacci — En informatique, un tas de Fibonacci est une structure de données similaire au tas binomial, mais avec un meilleur temps d exécution amorti. Les tas de Fibonacci ont été conçus par Michael L. Fredman et Robert E. Tarjan en 1984 et publiés pour la …   Wikipédia en Français

  • INFORMATIQUE - Évolution des systèmes de traitement de l’information — Un usage maintenant bien établi associe étroitement le mot «informatique» au principe du traitement de l’information à l’aide de machines électroniques perfectionnées. Sans insister sur l’ambiguïté de l’expression «traitement de l’information» et …   Encyclopédie Universelle

  • tas — ● n. m. ►MEM Bloc de mémoire utilisé par le système et les programmes pour faire un peu tout et n importe quoi. C est une zone de la mémoire sans grande organisation à ma connaissance. Syn. anglais heap …   Dictionnaire d'informatique francophone

  • Tas binomial — En informatique, un tas binomial est une structure de données assez proche du tas binaire, mais qui permet aussi de fusionner deux tas rapidement. Ainsi, il supporte les opérations suivantes, toutes en O(ln n): Insérer un nouvel élément au tas… …   Wikipédia en Français

  • Tas de Fibonacci — En informatique, un tas de Fibonacci est une structure de données similaire au tas binomial, mais avec un meilleur temps d exécution amorti. Les tas de Fibonacci ont été conçus par Michael L. Fredman et Robert E. Tarjan en 1984 et publiés pour la …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”