如何迭代Python中的優先級隊列？

我試圖在python中實現Uniform-cost search，爲此我需要一個優先級隊列，我使用標準庫中的queue.py。但是，算法的結尾會檢查隊列中是否存在成本較高的路徑。如果我的隊列中沒有任何給定的值，如果它不可迭代，我該如何檢查？如何迭代Python中的優先級隊列？

感謝

來源

2014-09-13 Rodrigo Souza

我建議使用簡單的'list'和'heapq'編寫自己的優先級隊列。它沒有那麼壞。請參閱heapq文檔中的[實現說明]（https://docs.python.org/2/library/heapq.html#priority-queue-implementation-notes）。 – roippi 2014-09-13 14:25:27

@roippi這就是'queue.PriorityQueue'的實現方式:) – dano 2014-09-13 16:27:51

除非你需要的線程安全性是queue.queue賦予它的主要目的在於爲線程安全的作業隊列，而不是作爲一種通用的隊列，您可直接使用collections.deque，因爲它們是可迭代會更好。

來源

2014-09-13 14:18:59

但我如何將它用作PriorityQueue？ – 2014-09-13 14:21:55

queue.PriorityQueue使用list實際執行，以及put/get方法使用heapq.heappush/heapq.heappop來維護list內的優先級排序。所以，如果你願意，你可以只遍歷內部列表，其中包含在queue屬性：

>>> from queue import PriorityQueue 
>>> q = PriorityQueue() 
>>> q.put((5, "a")) 
>>> q.put((3, "b")) 
>>> q.put((25, "c")) 
>>> q.put((2, "d")) 
>>> print(q.queue) 
[(2, 'd'), (3, 'b'), (25, 'c'), (5, 'a')]

來源

2014-09-13 16:25:10 dano

第一行應該是：從隊列導入PriorityQueue。請注意資本Q. – 2017-07-08 09:43:46

@SushilVerma是，對於Python 2.在Python 3.x中，它是小寫的q。 – dano 2017-07-08 12:41:34

作爲我的好朋友[T.佩恩（https://github.com/TPayneExperience）顯示在他的影片之一： '嘗試：進口隊列中排隊除了：進口隊列 <\blink> 而你覆蓋兩個 – WaveRider 2017-09-17 20:56:42

的PriorityQueue實現爲binary heap，這是使用Python中的list（陣列）來實現。要遍歷隊列，您需要知道有關孩子在列表中的存儲位置的規則。

規則是所有節點都有兩個孩子，除非他們是有孩子的最後一個孩子，否則他們可能會有一個孩子。在最後一個節點之後出現的所有節點都有零個子節點（duh）。

節點的子節點與節點自己在列表中的位置有關。其中i是那麼它的孩子被儲存於節點的列表索引：

2 * i + 1
2 * i + 2

然而，堆的唯一要求是，所有節點的孩子們一個大於或等於節點值的值（或大於取決於實現的值）。

例如，在上面關於binrary heap的鏈接wiki頁面中，您可以找到以下圖像。隊列中的第一項是根。非常明顯。第二項是根的孩子中較大的一個。但是，第三項可以是根節點的剩餘節點，也可以是隊列中第二個節點的任一子節點。也就是說，在隊列（25）中的第三項可能已經在相同的位置，無論是19或1

binary heap

因此，遍歷你需要保持所有當前曲目的隊列「可見」節點。例如：

def iter_priority_queue(queue): 

    if queue.empty(): 
     return 

    q = queue.queue 
    next_indices = [0] 
    while next_indices: 
     min_index = min(next_indices, key=q.__getitem__) 
     yield q[min_index] 
     next_indices.remove(mix_index) 
     if 2 * min_index + 1 < len(q): 
      next_indices.append(2 * min_index + 1) 
     if 2 * min_index + 2 < len(q): 
      next_indices.append(2 * min_index + 2)

該方法可以修補猴子在queue.PriorityQueue如果你感覺懶得做，但我會鼓勵你實現使用heapq模塊自己的優先級隊列類作爲PriorityQueue自帶了很多多餘的功能（主要是線程安全的，幾乎可以肯定不需要）。應該指出的是，上述方法是而不是線程安全。如果另一個線程在迭代過程中修改隊列，那麼上述方法將開始產生錯誤的數字，如果幸運的話可能會產生一個異常。

來源

2014-09-13 17:39:31 Dunes

如何迭代Python中的優先級隊列？

回答

相關問題