What is a Heap?
Leçon 2 sur 14 du cours Tas et files de priorité - Série sur les structures de données n°7 de Coddy.
Un tas (heap) est une structure de données en forme d'arbre qui respecte un invariant simple : chaque parent est plus petit que (ou égal à) ses enfants. La plus petite valeur se trouve toujours à la racine, prête à être lue en O(1). Cette variante particulière est appelée un min-heap ; l'image miroir avec un invariant de type "plus grand à la racine" est un max-heap.
L'astuce réside dans le stockage. Même si nous le concevons comme un arbre, un tas réside dans un tableau plat. Pour le nœud à l'indice i :
- Son parent est à l'indice
(i - 1) / 2. - Son enfant gauche est à l'indice
2 * i + 1. - Son enfant droit est à l'indice
2 * i + 2.
Pas de pointeurs, pas d'objets nœuds : juste des calculs d'indices. Cela rend les tas très efficaces pour le cache et faciles à implémenter.
Les cinq opérations principales sur un min-heap sont :
- Peek : Retourne la plus petite valeur (la racine).
- Insert : Ajoute une valeur et la fait remonter à sa place.
- ExtractMin : Supprime et retourne la plus petite valeur.
- Size : Retourne le nombre de valeurs stockées.
- IsEmpty : Vérifie si le tas est vide.
Créons une classe MinHeap !
Essayez vous-même
Cette leçon ne comprend pas de défi de code.
