1.5 實作優先級隊列

想要實作一個隊列,能夠以給定的優先級來對準榮盛排序,而且每次pop操作時候都會傳回優先級最高的那個元素

使用heapq子產品來實作一個簡單的優先級隊列

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]
           

簡單的使用

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)

print(q._queue)
print(q.pop())
print(q.pop())
print(q.pop())
           

輸出

[(-5, 1, Item(‘bar’)), (-1, 0, Item(‘foo’)), (-4, 2, Item(‘spam’)), (-1, 3, Item(‘grok’))]

Item(‘bar’)

Item(‘spam’)

Item(‘foo’)

如上所示，第一次pop傳回的bar是優先級最高的，具有相同優先級的foo和grok将依據插入順序傳回。

這個實作核心在用heapq，heapq.heappush插入元素到_queue清單中，heapq.heappop移除，而且寶追趕清單中第一個元素的優先級最低，heappop方法總是傳回最小的元素，是以這就是隊列能彈出正确元素的關鍵，就算N很大，效率也很高，因為push和pop操作都是O(logN)，N代表堆中元素的數量。

隊列在這個示例中以元組（-priority，index，item）的形式組成，把priority取複制是為了讓隊列能夠按照元素的優先級從高到低的順序排列，這和正常的堆排列從小到大的順序相反。

變量index的作用是把相同優先級的元素按照入隊順序排列，因為單單Item執行個體無法排序

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

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

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

輸出

Item(‘foo’)

Item(‘bar’)

Traceback (most recent call last):

File “/Users/zhangkun/Documents/GitHub/geektime/pycookbook.py”, line 26, in

a<b

TypeError: ‘<’ not supported between instances of ‘Item’ and ‘Item’

如果按照元組（priority,item）形式來表示元素，隻要優先級不同，就能比較，如果優先級相同就比較第二項，此時也會和上面一樣報錯

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

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

a = (1, Item('foo'))
b = (2, Item('bar'))

print(a<b)
c = (2, Item('ccc'))
d = (2, Item('ccc'))
print(c<d)
           

輸出：

True

Traceback (most recent call last):

File “/Users/zhangkun/Documents/GitHub/geektime/pycookbook.py”, line 28, in

print(c<d)

TypeError: ‘<’ not supported between instances of ‘Item’ and ‘Item’

不光有優先級，還通過引入額外的索引值建立元組（priority，index，item）就完全避免這個問題，因為沒有兩個元組index相同，一單比較操作的結果可以确定了，python就不會找再去比較剩下的元組其他元素了劃重點！！！

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

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


c = (2, 1,Item('ccc'))
d = (2, 2,Item('ccc'))
print(c<d)
           

輸出 True