Qu'est-ce qu'une pile?

Un tas (heap) est une structure de données arborescente particulière qui satisfait la propriété du tas. Cette propriété stipule que pour tout sommet, sauf la racine, la valeur de la clé de ce sommet doit être en relation spécifique avec la valeur de la clé de son parent. Il existe deux principaux types de tas :

• Tas max (Max-heap) : La valeur de la clé de chaque sommet n'est pas inférieure à celle de ses enfants. L'élément maximum se trouve à la racine.
• Tas min (Min-heap) : La valeur de la clé de chaque sommet n'est pas supérieure à celle de ses enfants. L'élément minimum se trouve à la racine.

Le tas est généralement implémenté sous forme de tableau, ce qui permet un accès efficace aux éléments et l'exécution d'opérations. La relation entre parent et enfants dans le tableau est la suivante :

• Pour un élément avec l'indice i (à partir de 0), son enfant gauche est à l'indice 2i + 1.
• Son enfant droit est à l'indice 2i + 2.
• Son parent est à l'indice floor((i - 1) / 2).

Opérations principales sur le tas :

• Insertion : Ajout d'un nouvel élément. Temps d'exécution O(log n), où n est le nombre d'éléments.
• Extraction-Max / Extraction-Min : Suppression et retour de l'élément maximum (dans un tas max) ou minimum (dans un tas min). Temps d'exécution O(log n).
• Heapify (Construction du tas) : Transformation d'un tableau arbitraire en un tas. Temps d'exécution O(n).

Les tas sont utilisés dans des algorithmes de tri (par exemple, tri par tas), dans des files d'attente de priorité, ainsi que dans des algorithmes de recherche de chemins les plus courts (par exemple, l'algorithme de Dijkstra).