在Python中插入時按值插入元素的數據結構

Question

我需要一個按插入值對元素（id，value）進行排序的隊列結構。另外，我需要能夠移除具有最高值的元素。我不需要這個結構是線程安全的。在Java中，我猜，這將對應於PriorirtyQueue。

我應該在Python中使用哪種結構？你能提供一個玩具的例子嗎？

Answer 1

您可以使用heapq模塊。

從文檔：

此模塊提供堆隊列算法， 又稱優先級隊列算法的實現。

Answer 2

Python有something similar（這是真的heapq線程安全包裝）：

from Queue import PriorityQueue 

q = PriorityQueue() 
q.put((-1, 'foo')) 
q.put((-3, 'bar')) 
q.put((-2, 'baz')) 

取而代之的是最大的，你可以用q.get()獲得最低數量：

>>> q.get() 
(-3, 'bar') 

如果您不喜歡底片，您可以覆蓋_get方法：

class PositivePriorityQueue(PriorityQueue): 
    def _get(self, heappop=max): 
     return heappop(self.queue) 

Answer 3

我認爲你在找什麼可以在heapq庫中找到。從http://docs.python.org/2/library/heapq.html：

Heap elements can be tuples. This is useful for assigning comparison values (such as task priorities) alongside the main record being tracked: 

>>> import heapq 
>>> 
>>> h = [] 
>>> heappush(h, (5, 'write code')) 
>>> heappush(h, (7, 'release product')) 
>>> heappush(h, (1, 'write spec')) 
>>> heappush(h, (3, 'create tests')) 
>>> heappop(h) 
(1, 'write spec') 

這是所期望的行爲？

Answer 4

heapq使用優先級隊列，但它是一個最小堆，因此您需要使值爲負。此外，由於排序是從左到右進行的，因此您需要將id放在第二位。

>>> import heapq 
>>> queue = [] 
>>> heapq.heappush(queue, (-1, 'a')) 
>>> heapq.heappush(queue, (-2, 'a')) 
>>> heapq.heappop(queue) 
(-2, 'a')