Qu'est-ce qu'une pile (dans le contexte des structures de données) ?

Un tas (heap) est un arbre spécialisé utilisé comme structure de données. La propriété principale du tas est l'ordre partiel : pour tout sommet, la valeur du sommet parent est supérieure ou égale à celle de ses enfants (max-heap) ou inférieure ou égale (min-heap).

Caractéristiques clés :

• Arbre binaire : Généralement implémenté comme un arbre binaire, où chaque nœud a au plus deux enfants.
• Arbre binaire complet : Sur tous les niveaux, sauf peut-être le dernier, l'arbre est complètement rempli. Les nœuds du dernier niveau sont remplis de gauche à droite. Cela permet de stocker efficacement le tas sous forme de tableau.
• Propriété du tas :
  • Max-heap : La valeur de chaque nœud est supérieure ou égale à celle de ses enfants. L'élément maximum est toujours à la racine.
  • Min-heap : La valeur de chaque nœud est inférieure ou égale à celle de ses enfants. L'élément minimum est toujours à la racine.

Opérations principales sur le tas :

• Insertion d'un élément : Ajouter un nouvel élément et maintenir la propriété du tas.
• Suppression d'un élément : Supprimer l'élément racine (le maximum ou le minimum, selon le type de tas) et maintenir la propriété du tas.
• Construction du tas : Construire un tas à partir d'un tableau d'éléments.

Applications du tas :

• Tri : Algorithme de tri par tas (Heapsort).
• Files de priorité : Implémentation efficace de files où les éléments sont traités par ordre de priorité.
• Algorithmes de recherche : Par exemple, recherche du k-ième élément en ordre de grandeur.
• Algorithmes sur les graphes : Par exemple, l'algorithme de Dijkstra.

Représentation du tas en tableau :

Étant donné que le tas est un arbre binaire complet, il peut être stocké efficacement dans un tableau sans utiliser de pointeurs.

• Si un nœud est à l'indice i, son enfant gauche est à l'indice 2*i + 1.
• Son enfant droit est à l'indice 2*i + 2.
• Son parent est à l'indice (i - 1) / 2.

# Exemple de représentation d'un min-heap sous forme de tableau
heap_array = [10, 15, 20, 17, 25, 30]

# Racine : heap_array[0] = 10
# Enfant gauche de la racine : heap_array[2*0 + 1] = heap_array[1] = 15
# Enfant droit de la racine : heap_array[2*0 + 2] = heap_array[2] = 20
# Parent de l'élément à l'indice 3 (17) : heap_array[(3-1)//2] = heap_array[1] = 15