python如何實現優先權隊列（附程式碼）

這篇文章帶給大家的內容是關於python如何實現優先權佇列（附程式碼），有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。

1、需求

我們想要實作一個佇列，它能夠以給定的優先權來對元素排序，並且每次pop作業時都會傳回優先權最高的那個元素

2、解決方案

利用heapq模組實作

程式碼：

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

運行結果：

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

上面的程式碼核心在於heapq模組的使用。函數heapq.heapqpush()以及heapq.heapqpop()分別實作將元素從列表_queue中插入和移除，且保證列表中第一個元素的優先權最低。 heappop()方法總是傳回【最小】的元素，因此這就是讓佇列能彈出正確元素的關鍵。此外，由於push和pop操作的複雜度都是O(logN),其中N代表堆中元素的數量，因此就算N的值很大，這些操作的效率也非常高。

上面程式碼中，佇列以元組(-priority ,index,item)的形式組成。把priority取負值是為了讓佇列能夠依照元素的優先權從高到底的順序排列。

變數index的作用是為了將具有相同優先權的元素以適當的順序排列。透過維護一個不斷遞增的索引，元素將以它們如佇列時的順序來排列。為了說明index的作用，看下面實例：

#程式碼：

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)

#

以上是python如何實現優先權隊列（附程式碼）的詳細內容。更多資訊請關注PHP中文網其他相關文章！