Présentation

Définition d'un tas (heap)

Un heap (tas) est une structure de type arbre, telle que les noeuds respectent une certaine relation d'ordre.

• Un max-heap est tel que chaque noeud père est supérieur (ou égal) à chacun de ses enfants.
• Un min-heap assure l'inverse.

Le module heapq implémente le min-heap.

Représentation sous forme de liste

Le module heapq permet de transformer la liste [19,9,4,10,11,8,2] en [2, 10, 4, 19, 11, 9, 8].

Et on a bien le résultat souhaité. En effet, si l'on range la seconde liste dans un arbre binaire parfait, on trouve un tas :

                 2                  
        10                4         
    19       11       9        8    
  ------------------------------------

Création d'un tas

Par réordonnancement à chaque nouvel élément

Une première manière de créer un tas est d'utiliser heappush() : le tas est réordonné à chaque nouvel élément inséré.

Prenons l'exemple suivant :

  >>> import heapq
  >>> heap = []
  >>> data = [19, 9, 4, 10, 11, 8, 2]

et itérons sur data :

  >>> for n in data:
  >>>     heapq.heappush(heap, n)
  >>> print heap
  [2, 10, 4, 19, 11, 9, 8]

Cela donne, en en faisant une représentation graphique :

                   2                  
          10                4         
      19       11       9        8    
  ------------------------------------

En réarangeant les éléments d'une liste

Si les données sont déjà en mémoire, il vaut mieux préférer heapify() à heappush() pour réarranger les éléments d'une liste (en faire un tas) :

  >>> import heapq
  >>> data = [19, 9, 4, 10, 11, 8, 2]

  >>> heapq.heapify(data)
  >>> print data
  [2, 10, 4, 19, 11, 9, 8]

Le calcul est plus rapide (et la liste a été remplacée).

Utilisation possible

Récupérer le plus petit élément

On suppose que l'on a un tas correctement ordonné.

La méthode heappop() retourne le plus petit élément du tas, et le supprime :

  >>> import heapq
  >>> data = [19, 9, 4, 10, 11, 8, 2]
  >>> heapq.heapify(data)

  >>> enordre = []
  >>> while data:
  >>>    pluspetit = heapq.heappop(data)
  >>>    print 'nouveau plus petit : ',pluspetit
  >>>    enordre.append(pluspetit)

Ce qui donne, pour notre exemple (si on le représente graphiquement) :

                   2                  
          9                 4         
      10       11       8        19   
  ------------------------------------
  nouveau plus petit : 2
  ------------------------------------
                   4                  
          9                 8         
      10       11       19   
  ------------------------------------
  nouveau plus petit : 4
  ------------------------------------
                   8                  
          9                 19        
      10       11   
  ------------------------------------
  (etc.)

Et alors :

  >>> print enordre
  [2, 4, 8, 9, 10, 11, 19]

Enlever le sommet du tas, et insérer un nouvel élément

On peut, en une seule opération :

• supprimer le sommet tas,
• insérer un autre élément,

tout en concervant la structure de tas.

La méthode associée à l'opération est heapreplace().

  >>> import heapq
  >>> data = [19, 9, 4, 10, 11, 8, 2]
  >>> heapq.heapify(data)

  >>> for n in [0, 7, 13, 9, 5]:
  >>>     pluspetit = heapq.heapreplace(data, n)
  >>>     print 'remplace ',pluspetit,' par ',n,' :'

                   2                  
          9                 4         
      10       11       8        19   
  ------------------------------------
  remplace 2 par 0 :
  ------------------------------------
                   0                  
          9                 4         
      10       11       8        19   
  ------------------------------------
  remplace 0 par 7 :
  ------------------------------------
                   4                  
          9                 7         
      10       11       8        19   
  (etc.)

De cette manière, on peut conserver un tas de taille fixée, par exemple un "queue of jobs" ordonné par priorité.

Récupération des plus petits éléments

Dans le module heapq existe la possibilité de récupérer les n plus petits (ou plus grands) éléments d'un itérable (liste, etc).

Ces méthodes nlargest() et nsmallest() ne sont réellement efficaces que pour de petites valeurs de n.

  >>> import heapq
  >>> data = [19, 9, 4, 10, 11, 8, 2]

  >>> print heapq.nlargest(3, data)
  [19, 11, 10]

  >>> print heapq.nsmallest(3, data)
  [2, 4, 8]

Ces valeurs peuvent s'obtenir autrement. Par exemple, avec list(reversed(sorted(data)[-3:])) et sorted(data)[:3] respectivement.