3.5　實現一個優先級隊列

在實際應用中，為了更便利地操作隊列，我們需要將隊列按優先級排序，并在隊列上的每次pop()操作后返回優先級最高的元素。

下面使用heapq模塊實現一個簡單的優先級隊列，相關代碼（priority_queue.py）如下：

---

# 優先級隊列
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]

---

優先級隊列的使用方式如下（priority_queue.py）：

---

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

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

if __name__ == "__main__":
    priority_queue = PriorityQueue()
    priority_queue.push(Item('queue_1'), 1)
    priority_queue.push(Item('queue_2'), 3)
    priority_queue.push(Item('queue_3'), 5)
    priority_queue.push(Item('queue_4'), 3)

    print(priority_queue.__dict__.get('_queue')[0])
    print(f'pop item is:{priority_queue.pop()}')

    print(priority_queue.__dict__.get('_queue')[0])
    print(f'pop item is:{priority_queue.pop()}')

    print(priority_queue.__dict__.get('_queue')[0])
    print(f'pop item is:{priority_queue.pop()}')

    print(priority_queue.__dict__.get('_queue')[0])
    print(f'pop item is:{priority_queue.pop()}')

    print(priority_queue.__dict__)

---

執行py文件，輸出結果如下：

---

(-5, 2, Item('queue_3'))
pop item is:Item('queue_3')
(-3, 1, Item('queue_2'))
pop item is:Item('queue_2')
(-3, 3, Item('queue_4'))
pop item is:Item('queue_4')
(-1, 0, Item('queue_1'))
pop item is:Item('queue_1')
{'_queue': [], '_index': 4}

---

由執行結果可知，第一個pop()操作返回了優先級最高的元素。

注意　如果兩個有著相同優先級的元素（queue_2和queue_4），pop()操作是按照它們被插入到隊列的順序返回的——先插入的元素先返回。

heapq.heappush()和heapq.heappop()函數分別用于在隊列_queue上插入和刪除第一個元素。隊列_queue保證第一個元素擁有最高優先級。

heappop()函數總是返回最小的的元素，這是保證隊列pop()操作返回正確元素的關鍵。另外，由于push()和pop()操作時間復雜度為O(logN)，其中N是堆的大小，因此即使N很大，執行操作的運行速度也很快。

在上面示例代碼中，隊列包含一個（-priority,index,item）的元組。設置優先級為負數的目的是使元素按照優先級從高到低排序。這與普通的按優先級從低到高排序的堆排序恰巧相反。

index變量的作用是保證同等優先級元素的正確排序。通過保存一個不斷增加的index下標變量，可確保元素按照它們插入的順序排序。index變量在相同優先級元素比較的情況下起到重要作用。

下面通過示例進一步講解優先級隊列，相關代碼（priority_queue_1.py）如下：

---

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

if __name__ == "__main__":
    queue_1 = Item('queue_1')
    queue_2 = Item('queue_2')
    print(queue_1 < queue_2)

---

執行py文件，輸出結果如下：

---

Traceback (most recent call last):
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter1/priority_queue_1.py", line 8, in <module>
    print(queue_1 < queue_2)
TypeError: '<' not supported between instances of 'Item' and 'Item'

---

如果你使用元組（priority,item），只要兩個元素的優先級不同就能比較。但當兩個元素優先級一樣時，比較操作就會出錯，這時我們可以在代碼priority_queue_1.py中做修改：

---

queue_1 = (1, Item('queue_1'))
queue_2 = (3, Item('queue_2'))
queue_3 = (1, Item('queue_3'))
print(queue_1 < queue_2)
print(queue_1 < queue_3)

---

輸出結果如下：

---

True
Traceback (most recent call last):
  File "/Users/lyz/Desktop/python-workspace/advanced_programming/chapter1/priority_queue_1.py", line 14, in <module>
    print(queue_1 < queue_3)
TypeError: '<' not supported between instances of 'Item' and 'Item'

---

由此可見，通過引入另外的index變量組成三元組（priority,index,item），能很好地避免上面示例中的錯誤，因為不可能有兩個元素有相同的index值。

Python在做元組比較時，如果前面的比較已經可以確定結果，后面的比較操作就不會發生了。我們可以繼續在priority_queue_1.py中添加如下修改：

---

queue_1 = (1, 0, Item('queue_1'))
queue_2 = (3, 1, Item('queue_2'))
queue_3 = (1, 2, Item('queue_3'))
print(queue_1 < queue_2)
print(queue_1 < queue_3)

---

執行py代碼，輸出結果如下：

---

True
True

---

如果想在多個線程中使用同一個隊列，那么需要增加適當的鎖和信號量機制。

有想深入了解heapq模塊的讀者可以仔細研讀heapq模塊的官方文檔。