How to implement priority queue in python (with code)

What this article brings to you is about how Python implements priority queues (with code). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

1. Requirements

We want to implement a queue that can sort elements with a given priority, and return the highest priority for each pop operation. That element

2. Solution

Use the heapq module to implement

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())

Running result:

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

The core of the above code lies in the use of the heapq module . The functions heapq.heapqpush() and heapq.heapqpop() implement inserting and removing elements from the list _queue respectively, and ensure that the first element in the list has the lowest priority. The heappop() method always returns the [smallest] element, so this is the key to popping the correct element from the queue. In addition, since the complexity of push and pop operations is O(logN), where N represents the number of elements in the heap, even if the value of N is large, the efficiency of these operations is very high.

In the above code, the queue is composed of tuples (-priority, index, item). The purpose of taking a negative value for priority is to allow the queue to be arranged in order from high to low priority of the elements.

The function of the variable index is to arrange elements with the same priority in the appropriate order. By maintaining an ever-increasing index, elements will be arranged in the order they appear in the queue. To illustrate the role of index, look at the following example:

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)

The above is the detailed content of How to implement priority queue in python (with code). For more information, please follow other related articles on the PHP Chinese website!