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
listsuffit :appendpour empiler,pop()pour dépiler, les deux en O(1). Il n'existe pas de classeStackdans 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'estcollections.dequeavecappendetpopleft, 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.heappushetheappopsont en O(log n),heap[0]donne le minimum en O(1), etheapifytransforme une liste existante en tas en O(n) — pas O(n log n).- Tas max
heapqne 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 utiliseheapq.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èveTypeErrors'ils ne sont pas ordonnables.
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.