Tas

Un tas est une structure de données composée de « nœuds » qui contiennent des valeurs. Un tas typique possède un nœud racine au sommet, qui peut avoir au moins deux nœuds enfants directement en dessous. Chaque nœud peut avoir au moins deux nœuds enfants, ce qui signifie que le tas s’élargit avec chaque nœud enfant. Lorsqu’il est représenté visuellement, un tas ressemble à un arbre inversé, et sa forme générale est celle d’un tas.

Bien que chaque nœud d’un tas puisse avoir au moins deux nœuds enfants (également appelés « enfants »), la plupart des tas limitent chaque nœud à deux enfants. Ces types de tas sont également appelés tas binaires et peuvent être utilisés pour stocker des données triées. Par exemple, un « tas binaire maximal » stocke la valeur la plus élevée dans le nœud racine. Les deuxième et troisième valeurs les plus élevées sont stockées dans les nœuds enfants du nœud racine. Dans tout l’arbre, chaque nœud possède une valeur supérieure à celle de chacun de ses nœuds enfants. Un « tas binaire minimal » est l’inverse : le nœud racine stocke la valeur la plus basse et chaque nœud possède une valeur inférieure à celle de ses enfants.

En informatique, les tas sont souvent représentés sous forme de schémas simples. Toutefois, le stockage réel des données dans un tas est plus complexe. Pour créer un tas, les programmeurs doivent écrire des algorithmes individuels pour insérer et supprimer des données. Les valeurs insérées dans un tas sont généralement stockées dans un tableau, qui peut être référencé par un programme. Comme les données d’un tas sont déjà triées, celui-ci constitue un moyen efficace de rechercher des valeurs précises.

NOTE: « Le tas » est également un terme de programmation qui peut être utilisé pour désigner de la mémoire allouée dynamiquement. Ce bloc de mémoire peut être accessible aux applications actives. Comme la mémoire du tas est allouée dynamiquement, sa taille peut augmenter ou diminuer selon la quantité de mémoire utilisée.