Le module heapq

Adresse : http://docs.python.org/3.3/library/heapq.html

Le module heapq implémente un modèle de liste triée “par tas”.

On dit qu’une liste L est un tas si, pour tout indice k dont les enfants existent, on a les inégalités : L[k] <= L[2*k + 1] et L[k] <= L[2*k + 2].

Tas binaire minimum représentant la liste [3, 5, 9, 7, 11, 13, 14, 8, 12, 15, 18, 17] — Représentation arborescente du tas binaire.

Par exemple, [3,5,9,7,11,13,14,8,12,15,18,17] est un tas, qu’il est commode de représenter sous forme arborescente.

Les opérations de maintien de la structure de tas (ajouts ou suppressions) y sont en temps logarithmique par rapport à la longueur de la liste. La valeur minimum est située au début du tas.

Remarque : les tas implémentés dans le module heapq sont des “tas-min” (chaque élément parent est inférieur ou égal à ses deux enfants), alors que l’habitude est plus souvent de considérer des “tas-max”. Pour la théorie, on se reportera à son livre favori sur l’algorithmique et les structures de données.

>>> from heapq import * # importe le module heapq (avec les noms courts)

>>> t1 = [3,17,11,14,9,12,8,18,5,15,13,7] # une liste

>>> heapify(t1); t1 # on transforme t1 en tas, sur place

[3, 5, 7, 14, 9, 11, 8, 18, 17, 15, 13, 12]

>>> t2 = [3,5,9,7,11,13,14,8,12,15,18,17] # mêmes éléments, mais c'est déjà un tas

>>> heapify(t2); t2 # heapify ne modifie donc pas t2

[3, 5, 9, 7, 11, 13, 14, 8, 12, 15, 18, 17]

>>> heappush(t2,10); t2 # ajoute 10 au tas t2, et maintient le tas

[3, 5, 9, 7, 11, 10, 14, 8, 12, 15, 18, 17, 13]

>>> heappop(t2); t2 # "poppe" le minimum, et actualise le tas t2

[5, 7, 9, 8, 11, 10, 14, 13, 12, 15, 18, 17]

>>> heappushpop(t2,16); t2 # ajoute 16, renvoie le minimum, maintient le tas

[7, 8, 9, 12, 11, 10, 14, 13, 16, 15, 18, 17] # voir aussi la fonction heapreplace

Le module heapq contient deux fonctions renvoyant la liste (ordonnée) des n plus grands (ou des n plus petits) éléments d’un itérable. C’est efficace si n n’est pas trop grand (sinon utiliser sorted) et si n != 1 (sinon utiliser min ou max).

>>> from random import sample

>>> a = sample(range(100,1000),10); a # liste de 10 entiers différents de trois chiffres

[961, 196, 764, 487, 759, 608, 426, 697, 553, 420]

>>> nlargest(3,a) # la liste des 3 plus grands

[961, 764, 759]

>>> nsmallest(4,a) # la liste des 4 plus petits

[196, 420, 426, 487]

>>> nsmallest(3,a,lambda x: x % 10) # les trois avec le plus petit reste modulo 10

[420, 961, 553]

>>> nsmallest(3,a,lambda x: abs(x-500)) # les trois plus proches de 500

[487, 553, 426]

Le module heapq contient également une fonction merge permettant de fusionner deux ou plusieurs itérables (supposés déjà triés dans l’ordre croissant) en un seul générateur (comme toujours avec les générateurs, l’ensemble des valeurs n’est pas chargé en mémoire en même temps, mais il est disponible à la demande dans un contexte d’itération) :

>>> x = [1, 5, 8, 15, 19, 23, 25, 31] # première liste croissante

>>> y = [2, 3, 6, 12, 14, 19, 26, 28, 30] # deuxième liste croissante

>>> z = [2, 10, 20, 40] # troisième liste croissante

>>> merge(x,y,z) # on les fusionne en un seul générateur

>>> list(merge(x,y,z)) # si on veut voir toutes les valeurs d'un coup

[1, 2, 2, 3, 5, 6, 8, 10, 12, 14, 15, 19, 19, 20, 23, 25, 26, 28, 30, 31, 40]

Le module heapq

Retour à l’accueil du cours Python/Numpy

Sommaire du chapitre 7