File de priorité en Python avec heapq : tas, priorités et exemples

heapq est le module Python standard pour manipuler un tas binaire. En pratique, on l’utilise surtout pour créer une file de priorité : à chaque retrait, on récupère l’élément avec la plus petite priorité.

Ce mécanisme est central dans plusieurs algorithmes : Dijkstra, Prim, A*, planification de tâches, files d’événements, top-k, fusion de listes triées ou traitement par score.

La réponse courte

En Python, une file de priorité avec heapq ressemble à ceci :

import heapq


file = []

heapq.heappush(file, (3, "tache basse"))
heapq.heappush(file, (1, "tache urgente"))
heapq.heappush(file, (2, "tache normale"))

while file:
    priorite, tache = heapq.heappop(file)
    print(priorite, tache)

Résultat :

1 tache urgente
2 tache normale
3 tache basse

Par défaut, heapq est un min-heap : la plus petite priorité sort en premier.

Pourquoi heapq est utile

Une file classique traite les éléments dans leur ordre d’arrivée. Une file de priorité traite l’élément le plus important selon une valeur de priorité.

Les opérations principales sont :

Transformer une liste en tas

Si vous avez déjà une liste, utilisez heapify.

import heapq


valeurs = [9, 3, 7, 1, 5]
heapq.heapify(valeurs)

print(heapq.heappop(valeurs))
print(heapq.heappop(valeurs))

La liste interne n’est pas triée comme avec sorted(). Elle respecte seulement la propriété du tas : le plus petit élément est en première position.

Gérer des objets avec des tuples

En Python, la technique courante consiste à stocker des tuples :

(priorite, donnee)

Exemple :

import heapq


evenements = []

heapq.heappush(evenements, (10, "sauvegarde"))
heapq.heappush(evenements, (3, "alerte"))
heapq.heappush(evenements, (7, "rapport"))

print(heapq.heappop(evenements))

Si deux priorités sont égales et que les données ne sont pas comparables, ajoutez un compteur.

import heapq
from itertools import count


compteur = count()
file = []

heapq.heappush(file, (1, next(compteur), {"nom": "A"}))
heapq.heappush(file, (1, next(compteur), {"nom": "B"}))

print(heapq.heappop(file)[2])

Le compteur sert à départager les égalités sans comparer directement les dictionnaires.

Exemple : top-k éléments

Pour récupérer les k plus grandes valeurs, utilisez nlargest.

import heapq


scores = [41, 12, 88, 53, 77, 19]

print(heapq.nlargest(3, scores))
print(heapq.nsmallest(2, scores))

Pour de petites listes, sorted() est souvent plus simple. heapq devient surtout intéressant quand k est petit par rapport au nombre total d’éléments.

Exemple : squelette de Dijkstra

Dijkstra utilise une file de priorité pour toujours explorer le sommet avec la plus petite distance connue.

import heapq


def dijkstra(graphe, depart):
    distances = {depart: 0}
    file = [(0, depart)]

    while file:
        distance, sommet = heapq.heappop(file)

        if distance > distances.get(sommet, float("inf")):
            continue

        for voisin, poids in graphe[sommet]:
            nouvelle = distance + poids

            if nouvelle < distances.get(voisin, float("inf")):
                distances[voisin] = nouvelle
                heapq.heappush(file, (nouvelle, voisin))

    return distances


graphe = {
    "A": [("B", 4), ("C", 2)],
    "B": [("D", 5)],
    "C": [("B", 1), ("D", 8)],
    "D": [],
}

print(dijkstra(graphe, "A"))

Cette version peut contenir plusieurs entrées pour un même sommet dans le tas. Ce n’est pas un bug : on ignore les entrées devenues obsolètes avec le test if distance > distances.get(...).

Pour un guide complet sur les graphes, voir Algorithmes de graphes en Python.

Max-heap en Python

heapq fournit un min-heap. Pour simuler un max-heap, on utilise souvent des priorités négatives.

import heapq


file = []

for score in [10, 30, 20]:
    heapq.heappush(file, -score)

print(-heapq.heappop(file))

Cette technique est simple, mais il faut rester cohérent : toutes les priorités doivent être inversées de la même façon.

Erreurs fréquentes

La première erreur est de croire que la liste du tas est triée. Seul l’élément d’index 0 est garanti comme minimum.

La deuxième erreur est d’utiliser heapq sans tuple de priorité. Si vous empilez directement des objets complexes, Python doit savoir les comparer.

La troisième erreur est de vouloir supprimer ou modifier une priorité au milieu du tas. heapq ne fournit pas directement de decrease-key. Dans Dijkstra et Prim, on empile souvent une nouvelle priorité et on ignore l’ancienne quand elle ressort.

La quatrième erreur est de choisir heapq pour tout. Une file FIFO simple doit rester un deque, pas un tas.

Où continuer

heapq est une structure charnière dans le cluster algorithmes :

• Algorithmes Python : tous les guides pour apprendre pas à pas
• Algorithme de Prim en Python avec heapq
• Prim vs Kruskal en Python
• Complexité algorithmique en Python

La règle à retenir : utilisez heapq quand vous devez récupérer souvent l’élément de plus petite priorité sans retrier toute la collection.

Références

• Documentation Python – heapq
• Documentation Python – itertools.count
• Documentation Python – structures de données