Tas et files de priorité
Qu'est-ce qu'un tas (heap) ?
Un tas est un arbre binaire complet où chaque parent respecte la propriété de tas - toujours plus petit (min-heap) ou toujours plus grand (max-heap) que ses enfants. « Complet » signifie que chaque niveau est rempli sauf éventuellement le dernier, qui se remplit de gauche à droite.
1 Min-heap
/ \
3 5
/ \
7 4
Comme il est complet, on le stocke dans un tableau à plat - pas besoin de pointeurs. Pour l'index i : enfant gauche = 2i + 1, enfant droit = 2i + 2, parent = (i - 1) // 2.
Min-Heap vs Max-Heap
| Propriété | Min-Heap | Max-Heap | |-----------|----------|----------| | Racine | Plus petit élément | Plus grand élément | | Parent ≤ Enfants ? | ✅ Oui | ❌ Non (≥) | | Extraction donne | Minimum | Maximum |
Le module heapq de Python est un min-heap par défaut. Pour un max-heap, on inverse les valeurs à l'insertion et à l'extraction.
Insertion et extraction - Étape par étape
Insertion - ajouter en fin, puis remonter (échanger avec le parent tant que plus petit) :
import heapq
h = [1, 3, 5, 7]
heapq.heappush(h, 2) # h becomes [1, 2, 5, 7, 3]
Extraction du minimum - échanger la racine avec le dernier élément, retirer le dernier, puis descendre (échanger avec le plus petit enfant) :
smallest = heapq.heappop(h) # returns 1
Les deux opérations s'exécutent en O(log n) car la hauteur de l'arbre est log n.
Discussion
Sign in to join the discussion