backend / algorithmes-structures-donnees
Tas (heaps) et files de priorité
Explication
Ce que vous allez apprendre
- Expliquer la propriété d'ordre partiel d'un tas (min-heap / max-heap) et pourquoi elle est plus faible qu'un tri complet
- Représenter un tas comme un simple tableau et retrouver parent et enfants par calcul d'index
- Implémenter les opérations "remonter" (sift-up) et "descendre" (sift-down) lors d'une insertion et d'une extraction
- Justifier pourquoi ces opérations restent en O(log n) grâce à la hauteur logarithmique du tas
- Utiliser un tas comme file de priorité pour toujours traiter l'élément le plus urgent en premier
Dans quel contexte ?
Un système de traitement de tickets de support doit toujours traiter en premier le ticket de priorité la plus haute, même si des dizaines de nouveaux tickets moins urgents arrivent entre-temps. Trier la liste complète à chaque nouvel arrivage coûterait O(n log n) à chaque fois. Avec un tas (via heapq en Python), insérer un ticket coûte O(log n) et récupérer le plus urgent coûte O(log n) également, sans jamais trier l'ensemble — c'est exactement le mécanisme derrière l'ordonnancement des tâches dans de nombreux systèmes de files d'attente.
D'abord, une question plus modeste que "trier"
Trier tout un tableau juste pour connaître son minimum est un gaspillage : il existe une structure qui répond à "quel est le minimum actuel ?" bien plus efficacement, sans jamais trier l'ensemble.
L'idée centrale d'un tas
Un tas ne garantit qu'une seule chose : le plus petit (min-heap) ou le plus grand (max-heap) élément est toujours accessible instantanément à la racine. C'est un ordre partiel, beaucoup plus faible qu'un tri complet, mais suffisant pour cette question précise.
Piège fréquent
Un tas garantit seulement l'ordre entre un parent et ses enfants, pas entre les deux enfants eux-mêmes, ni entre les noeuds de branches différentes. Parcourir un tas dans l'ordre du tableau ne donne donc PAS une liste triée — pour l'obtenir, il faut extraire les éléments un par un.
Étape 1 : comment un tas est organisé
Un tas est représenté comme un arbre binaire quasi complet, concrètement un simple tableau. La seule règle à respecter : chaque parent est plus petit (ou plus grand) que ses deux enfants — rien n'impose d'ordre entre les deux enfants eux-mêmes, contrairement à un BST.
Étape 2 : insérer un élément
Un nouvel élément est d'abord placé en bout de tableau, puis on le fait "remonter" tant qu'il viole la règle avec son parent, en les échangeant.
Étape 3 : extraire le minimum
On remplace la racine par le dernier élément du tableau, puis on fait "descendre" ce nouvel élément vers ses enfants tant qu'il viole la règle.
| Opération | Coût | Ce qui se passe |
|---|---|---|
| Insertion (push) | O(log n) | Ajout en fin de tableau puis remontée (sift-up) |
| Extraction du min/max (pop) | O(log n) | Racine remplacée par le dernier élément puis descente (sift-down) |
| Consulter le min/max | O(1) | Toujours à la racine, index 0 |
| Trier tout le tas | O(n log n) | n extractions successives (heap sort) |
Pourquoi ces deux opérations sont rapides
Chacune ne parcourt qu'un seul chemin entre la racine et une feuille, de longueur log2(n) : c'est cette règle plus faible qu'un BST qui rend le tas plus simple et tout aussi rapide, en O(log n).
Astuce
Le module heapq de Python n'implémente qu'un min-heap. Pour simuler un max-heap, la ruse classique consiste à stocker l'opposé de chaque valeur (-valeur) et à l'inverser à nouveau à la lecture.
Pour aller plus loin : la file de priorité
Une file de priorité doit toujours traiter l'élément le plus urgent en premier, quel que soit l'ordre d'arrivée. C'est exactement la garantie qu'offre un tas, sans jamais avoir besoin de trier quoi que ce soit.
Un pattern à retenir
Chercher les k plus grands éléments d'un tableau avec un tas coûte O(n log k), bien mieux que trier tout le tableau en O(n log n) quand k est petit devant n.
Vers la suite
Toutes les structures vues jusqu'ici organisaient des données individuelles. La prochaine leçon change d'échelle et s'attaque à la modélisation de relations entre des entités : les graphes.
Commandes & code
Tas (heaps) et files de priorité
import heapq
# --- heapq de Python : min-heap sur une simple liste ---
tas: list[int] = []
heapq.heappush(tas, 5)
heapq.heappush(tas, 1)
heapq.heappush(tas, 8)
heapq.heappush(tas, 3)
plus_petit = heapq.heappop(tas) # O(log n) : retire et retourne le minimum -> 1
minimum_sans_retirer = tas[0] # O(1) : le minimum est toujours à l'index 0
# Convertir une liste existante en tas : O(n), plus rapide que n insertions O(n log n)
donnees = [9, 4, 7, 1, 3, 8]
heapq.heapify(donnees) # transforme la liste EN PLACE en min-heap
# Max-heap : Python ne fournit qu'un min-heap -- on inverse le signe
tas_max: list[int] = []
for valeur in [5, 1, 8, 3]:
heapq.heappush(tas_max, -valeur) # on stocke l'opposé
maximum = -heapq.heappop(tas_max) # on ré-inverse à la sortie -> 8
# --- Implémentation manuelle d'un min-heap (pour comprendre le mécanisme interne) ---
class MinHeap:
def __init__(self):
self._donnees: list[int] = []
def _parent(self, i: int) -> int: return (i - 1) // 2
def _gauche(self, i: int) -> int: return 2 * i + 1
def _droite(self, i: int) -> int: return 2 * i + 2
def inserer(self, valeur: int) -> None:
self._donnees.append(valeur)
self._remonter(len(self._donnees) - 1) # O(log n)
def _remonter(self, i: int) -> None:
while i > 0 and self._donnees[self._parent(i)] > self._donnees[i]:
p = self._parent(i)
self._donnees[i], self._donnees[p] = self._donnees[p], self._donnees[i]
i = p
def extraire_min(self) -> int:
if not self._donnees:
raise IndexError("Tas vide")
minimum = self._donnees[0]
dernier = self._donnees.pop()
if self._donnees:
self._donnees[0] = dernier
self._descendre(0) # O(log n)
return minimum
def _descendre(self, i: int) -> None:
taille = len(self._donnees)
while True:
plus_petit = i
g, d = self._gauche(i), self._droite(i)
if g < taille and self._donnees[g] < self._donnees[plus_petit]:
plus_petit = g
if d < taille and self._donnees[d] < self._donnees[plus_petit]:
plus_petit = d
if plus_petit == i:
break
self._donnees[i], self._donnees[plus_petit] = self._donnees[plus_petit], self._donnees[i]
i = plus_petit
def __len__(self) -> int:
return len(self._donnees)
h = MinHeap()
for v in [5, 1, 8, 3, 9]:
h.inserer(v)
assert [h.extraire_min() for _ in range(len(h))] == [1, 3, 5, 8, 9]
# --- File de priorité avec tuples (priorité, valeur) : pattern très courant ---
file_priorite: list[tuple[int, str]] = []
heapq.heappush(file_priorite, (2, "tâche moyenne"))
heapq.heappush(file_priorite, (1, "tâche urgente"))
heapq.heappush(file_priorite, (3, "tâche basse"))
while file_priorite:
priorite, tache = heapq.heappop(file_priorite) # traite toujours la priorité la plus basse d'abord
print(priorite, tache)
# Application classique : les K plus grands/petits éléments SANS trier tout le tableau
def k_plus_grands(tableau: list[int], k: int) -> list[int]:
# O(n log k) : bien meilleur que trier tout O(n log n) quand k << n
return heapq.nlargest(k, tableau)
def k_plus_petits(tableau: list[int], k: int) -> list[int]:
return heapq.nsmallest(k, tableau)
# Application classique : fusionner K listes triées efficacement
def fusionner_k_listes_triees(listes: list[list[int]]) -> list[int]:
return list(heapq.merge(*listes)) # O(n log k), utilise un tas en interne
assert fusionner_k_listes_triees([[1, 4, 7], [2, 5, 8], [3, 6, 9]]) == list(range(1, 10))
# Application classique : médiane glissante avec deux tas (max-heap + min-heap)
class MedianeGlissante:
def __init__(self):
self._bas: list[int] = [] # max-heap (valeurs inversées) -- moitié inférieure
self._haut: list[int] = [] # min-heap -- moitié supérieure
def ajouter(self, nombre: int) -> None:
heapq.heappush(self._bas, -nombre)
heapq.heappush(self._haut, -heapq.heappop(self._bas))
if len(self._haut) > len(self._bas):
heapq.heappush(self._bas, -heapq.heappop(self._haut))
def mediane(self) -> float:
if len(self._bas) > len(self._haut):
return float(-self._bas[0])
return (-self._bas[0] + self._haut[0]) / 2Résumé
- Un tas garantit accès O(1) au minimum (ou maximum), insertion/extraction en O(log n), construction en O(n) via
heapify. heapqde Python n'implémente qu'un min-heap : inverser le signe pour simuler un max-heap.- Pattern "k plus grands/petits" :
heapq.nlargest/nsmallesten O(n log k), bien meilleur qu'un tri complet. - Pattern "médiane glissante" : deux tas (max-heap pour la moitié basse, min-heap pour la moitié haute) maintenus équilibrés.
Exercices pratiques
Mission : réparer le système de tickets qui traite les urgences en retard
Objectif : Diagnostiquer un mauvais usage de heapq et raisonner sur le coût comparé tri complet contre tas.
Contexte
Le système de support technique reçoit des tickets en continu, chacun avec un niveau de priorité. Un développeur a implémenté la file avec tickets.sort() rappelé après chaque nouvel ajout, pour toujours traiter le ticket le plus urgent en premier. Sous forte charge (des centaines d'arrivées par minute), le service commence à ralentir dangereusement, et des tickets urgents attendent parfois plusieurs minutes derrière ce tri répété.