Implémenter une file de priorité

Vous souhaitez implémenter une file (queue) qui trie les éléments selon une priorité donnée et qui retourne toujours l’élément avec la priorité la plus élevée à chaque opération de retrait (pop).

La classe suivante utilise le module heapq pour implémenter une file de priorité simple :

import heapq


class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0

    def push(self, item, priority):
        heapq.heappush(self._queue, (-priority, self._index, item))
        self._index += 1

    def pop(self):
        return heapq.heappop(self._queue)[-1]

Voici un exemple de la manière dont elle pourrait être utilisée :

class Item:
    def __init__(self, name):
        self.name = name

    def __repr__(self):
        return 'Item({!r})'.format(self.name)

q = PriorityQueue()
q.push(Item('foo'), 1)
q.push(Item('bar'), 5)
q.push(Item('spam'), 4)
q.push(Item('grok'), 1)
q.pop()
print(Item('bar'))
q.pop()
print(Item('spam'))
q.pop()
print(Item('foo'))
q.pop()
print(Item('grok'))

Remarquez que la première opération pop() a retourné l’élément avec la priorité la plus élevée. Notez également que les deux éléments ayant la même priorité (foo et grok) ont été retournés dans le même ordre que celui dans lequel ils ont été insérés dans la file.

L’élément central de cette recette concerne l’utilisation du module heapq. Les fonctions heapq.heappush() et heapq.heappop() insèrent et retirent des éléments d’une liste _queue de manière à ce que le premier élément de la liste ait la plus petite priorité (comme discuté dans l'article : « Trouver les N plus grands ou plus petits éléments »). La méthode heappop() retourne toujours l’élément ayant la plus petite valeur, ce qui est la clé pour faire en sorte que la file retourne les bons éléments lors du pop(). De plus, comme les opérations de push et de pop ont une complexité en O(log N), où N est le nombre d’éléments dans le tas, ces opérations restent assez efficaces même lorsque N est relativement grand.

Dans cet article, la file est constituée de tuples de la forme (priorité, index, élément). La priorité est négativée afin que la file trie les éléments de la priorité la plus élevée à la plus faible. C’est l’inverse du comportement normal d’un heap, qui trie par ordre croissant.

Le rôle de la variable index est d’assurer un ordre correct entre les éléments ayant le même niveau de priorité. En utilisant un index constamment croissant, les éléments sont triés selon leur ordre d’insertion. Cependant, cet index joue aussi un rôle important dans les opérations de comparaison, lorsque plusieurs éléments ont la même priorité. Pour développer cela : les instances de Item dans l’exemple ne sont pas comparables entre elles. Cela vous retournera une erreur. Par exemple :

a = Item('foo')
b = Item('bar')

print(a < b)

Si vous créez des tuples de la forme (priorité, élément), ils peuvent être comparés tant que les priorités sont différentes. Cependant, si deux tuples avec des priorités égales sont comparés, la comparaison échoue comme précédemment. Par exemple :

a = (1, Item('foo'))
b = (5, Item('bar'))
print(a < b) # True

En introduisant un index supplémentaire et en créant des tuples de la forme (priorité, index, élément), vous évitez complètement ce problème, puisque aucun tuple n’aura jamais la même valeur d’index. Et Python n’essaie jamais de comparer les valeurs suivantes du tuple une fois que le résultat de la comparaison peut être déterminé.

a = (1, 0, Item('foo'))
b = (5, 1, Item('bar'))
c = (1, 2, Item('grok'))
print(a < b) # True
print(a < c) # True

Si vous souhaitez utiliser cette file pour la communication entre threads, vous devez ajouter les mécanismes de verrouillage (locking) et de signalement (signaling) appropriés. La documentation du module heapq contient également d’autres exemples et des explications plus approfondies sur la théorie et l’implémentation des tas (heaps).

Publié le

me contacter

* champ obligatoire