Formations — 1 037 leçons en français

Accueil › Python › Piles, files et tas : deque, heapq et le piège de pop(0)

Piles, files et tas : deque, heapq et le piège de pop(0)

Algorithmique d'entretienavance

Trois structures, trois mots-clés, et un piège qui vaut la leçon à lui seul.

Pile : une list suffit, les deux opérations sont en O(1).

pile: list[str] = []
pile.append("étape 1")     # empiler  — O(1)
pile.append("étape 2")
pile.pop()                 # dépiler  — O(1), rend "étape 2"

File : surtout pas une list.

from collections import deque

file = deque(["c1", "c2"])
file.append("c3")          # O(1)
file.popleft()             # O(1)  — rend "c1"

list.pop(0) fait la même chose, mais en O(n) : il faut décaler les n - 1 éléments restants. Sur une file de cent mille éléments, le traitement complet passe de O(n) à O(n²).

Tas : heapq, dans une liste ordinaire.

import heapq

tas: list[tuple[int, str]] = []
heapq.heappush(tas, (2, "livraison"))      # O(log n)
heapq.heappush(tas, (1, "remboursement"))
tas[0]                                      # (1, 'remboursement') — le minimum, O(1)
heapq.heappop(tas)                          # retire le minimum, O(log n)

Deux faits à ne pas oublier : heapq est un tas min uniquement — pour les plus grands, poussez l'opposé — et seul tas[0] est à sa place. Une deque en revanche se parcourt dans l'ordre sans problème.

Les termes à connaître

Pile (LIFO)

Dernier entré, premier sorti. En Python, une list suffit : append pour empiler, pop() pour dépiler, les deux en O(1). Il n'existe pas de classe Stack dans la bibliothèque standard, et il n'en faut pas.

File (FIFO)

Premier entré, premier sorti. Pas une list : pop(0) est en O(n). C'est collections.deque avec append et popleft, tous deux en O(1).

deque

« Double-ended queue » : une suite de blocs chaînés dont les deux extrémités s'ajoutent et se retirent en O(1) (append, appendleft, pop, popleft). En contrepartie, l'accès par index au milieu est en O(n).

maxlen

deque(maxlen=k) garde au plus k éléments : au-delà, chaque ajout d'un côté expulse silencieusement l'élément de l'autre côté. Une fenêtre glissante ou un journal des k derniers événements en une ligne.

heapq

Module qui gère un tas min directement dans une list. heappush et heappop sont en O(log n), heap[0] donne le minimum en O(1), et heapify transforme une liste existante en tas en O(n) — pas O(n log n).

Tas max

heapq ne fournit que le tas min. Pour obtenir les plus grands, on stocke l'opposé des valeurs (heappush(tas, -x)) et on inverse au retrait, ou on utilise heapq.nlargest.

Compteur de départage (tie-breaker)

Un entier croissant inséré dans le tuple poussé sur le tas, entre la priorité et l'objet : (priorite, compteur, objet). Il évite que deux priorités égales forcent la comparaison des objets, qui lève TypeError s'ils ne sont pas ordonnables.

Lire l'explication détaillée et faire le quiz →

Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.