Python中的優先級隊列

優先隊列的堆實現

Source

優先級隊列是一種與普通隊列或堆棧相似的數據結構，但是每個元素都具有關聯的優先級。 高優先級的元素先於低優先級的元素提供。 優先級隊列通常使用堆數據結構來實現。

在本文中，我們將討論使用堆數據結構在python中實現優先級隊列的方法。

讓我們開始吧！

在構建" PriorityQueue"類之前，值得熟悉python" heapq"模塊。 首先，我們導入" heapq"模塊：

<code>import heapq/<code>

假設我們有一個IBM的歷史價格清單：

<code>ibm_prices = [108.68, 109.65, 121.01, 122.78, 120.16]/<code>

如果我們想獲得N的最低價格或最高價格，可以分別使用" .nsmallest（）"和" .nlargest（）"方法。 要獲得三個最低價格，我們可以執行以下操作：

<code>print(heapq.nsmallest(3, ibm_prices))/<code>

對於三個最高價格：

<code>print(heapq.nlargest(3, ibm_prices))/<code>

為了使事情變得更有趣，假設我們有一個科技公司股票組合：

<code>portfolio = [
       {'name': 'IBM', 'shares': 200, 'price': 108.68},
       {'name': 'AAPL', 'shares': 75, 'price': 277.97},
       {'name': 'FB', 'shares': 40, 'price': 170.28},
       {'name': 'HPQ', 'shares':125, 'price': 17.18},
       {'name': 'UBER', 'shares': 50, 'price': 22.60}, 

       {'name': 'TWTR', 'shares': 95, 'price': 29.29}
]/<code>

我們可以使用" .nsmallest（）"和" .nlargest（）"分別提取最便宜和最昂貴的股票：

<code>cheap_stocks = heapq.nsmallest(3, portfolio, key=lambda s: s['price'])
expensive_stocks = heapq.nlargest(3, portfolio, key=lambda s: s['price'])/<code>

讓我們打印結果：

<code>pprint("Cheap Stocks: ", cheap_stocks)
print("Expensive Stocks: ", expensive_stocks)/<code>

這些功能提供了卓越的性能，特別是當N個元素的大小（最大或最小）與整個集合相比較小時。

現在，我們可以構建優先級隊列類了。 讓我們使用" heapq"模塊創建優先級隊列類。 首先，我們創建初始化方法：

<code>class PriorityQueue:
    def __init__(self):
        self._queue = []
        self._index = 0/<code>

我們還定義一個方法，該方法將允許我們檢查隊列是否為空：

<code>class PriorityQueue:
    ...
    def is_empty(self):
        return not self._queue/<code>

接下來，讓我們定義一個方法，該方法將允許我們將對象推送到優先級隊列中。 我們採用" heappush"方法，該方法將具有優先級和項目值：

<code>class PriorityQueue:
    ...
    def push(self, item, priority):
        heapq.heappush(self._queue, (priority, self._index, item))
        self._index += 1/<code>

最後，我們將使用'heappop'方法添加一個方法，使我們可以從優先級隊列中刪除元素：

<code>class PriorityQueue:
    ...
    def pop(self):
        return heapq.heappop(self._queue)[-1]/<code>

接下來，我們定義一個名為Stock的類，該類將用於演示優先級隊列類的用法。 該類將具有" init"方法，該方法可讓我們初始化股價，股票和股票代碼的值：

<code>class Stock:
    def __init__(self, stock_ticker, stock_price, stock_share):
        self.stock_ticker = stock_ticker
        self.stock_price = stock_price
        self.stock_share = stock_share/<code>

我們還可以定義一個方法，使我們可以打印類屬性的表示形式：

<code>class Stock:
    ...
    def __repr__(self):
        return 'Stock({}, {}, {})'.format(self.stock_ticker ,   self.stock_price,  self.stock_share)/<code>

現在我們準備初始化優先級隊列並添加項目：

<code>q = PriorityQueue()/<code>

讓我們將初始投資組合中的股票屬性添加到優先級隊列中。 我們將優先處理廉價股票：

<code>q.push(Stock('IBM', 108.68, 200), 4)
q.push(Stock('HPQ', 17.18, 125), 1)
q.push(Stock('TWTR', 29.29, 95), 3)
q.push(Stock('UBER', 22.6, 50), 2)
q.push(Stock('AAPL', 277.97, 75), 6)
q.push(Stock('FB', 170.28, 40), 5)/<code>

現在，讓我們在優先級隊列中打印項目：

<code>while not q.is_empty():
    print(q.pop())/<code>

我將在這裡停止，但可以隨意使用優先級隊列的堆實現。 此外，您可以嘗試使用普通列表或鏈接列表構建優先級隊列。 您可以在python中找到其他優先級隊列實現的一些示例。 我希望您發現這篇文章有用/有趣。 這篇文章中的代碼可在GitHub上找到。 感謝您的閱讀！

(本文翻譯自Sadrach Pierre, Ph.D.的文章《Priority Queues in Python》，參考：https://towardsdatascience.com/priority-queues-in-python-3baf0bac2097)

閱讀更多 聞數起舞 的文章

關鍵字: IBM 數據結構 優先級