Comment implémenter la file d'attente prioritaire en python (avec code)

Ce que cet article vous apporte concerne la façon dont Python implémente les files d'attente prioritaires (avec du code). Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

1. Exigences

Nous souhaitons implémenter une file d'attente qui peut trier les éléments avec une priorité donnée et renvoyer l'élément la plus prioritaire pour chaque opération pop

<.>2. SolutionUtiliser le module heapq pour implémenter

Code :

import heapq

#利用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]

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

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

if __name__ == '__main__':
    q=PriorityQueue()
    q.push(Item('foo'),1)
    q.push(Item('bar'),5)
    q.push(Item('spam'),4)
    q.push(Item('grok'),1)

    print(q.pop())
    print(q.pop())
    #具有相同优先级的两个元素，返回的顺序同它们插入到队列时的顺序相同
    print(q.pop())
    print(q.pop())

Exécuter le résultat :

Le cœur du code ci-dessus est l'utilisation du module heapq . Les fonctions heapq.heapqpush() et heapq.heapqpop() implémentent respectivement l'insertion et la suppression d'éléments de la liste _queue et garantissent que le premier élément de la liste a la priorité la plus basse. La méthode heappop() renvoie toujours le [plus petit] élément, c'est donc la clé pour extraire le bon élément de la file d'attente. De plus, étant donné que la complexité des opérations push et pop est O(logN), où N représente le nombre d'éléments dans le tas, même si la valeur de N est grande, l'efficacité de ces opérations est très élevée.

Item('bar')
Item('spam')
Item('foo')
Item('grok')

Dans le code ci-dessus, la file d'attente est composée de tuples (-priority, index, item). Le but de prendre une valeur négative pour la priorité est de permettre à la file d'attente d'être organisée par ordre de priorité élevée à faible des éléments.

La fonction de l'index variable est d'organiser les éléments avec la même priorité dans l'ordre approprié. En maintenant un index toujours croissant, les éléments seront classés dans l'ordre dans lequel ils apparaissent dans la file d'attente. Pour illustrer le rôle de l'index, regardez l'exemple suivant :

Code :

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

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

if __name__ == '__main__':
    a=(1,Item('foo'))
    b=(5,Item('bar'))
    #下面一句打印True
    print(a<b)


    c=(1,Item('grok'))
    #下面一句会报错：TypeError: '<' not supported between instances of 'Item' and 'Item'
    print(c<a)


    d=(1,0,Item('foo'))
    e=(5,1,Item('bar'))
    f=(1,2,Item('grok'))
    #下面一句打印True
    print(d<e)
    #下面一句打印True
    print(d<f)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!