# top - python queue用法

## Python的通用優先級隊列 (6)

``````from heapq import *

heap = []
data = [(10,"ten"), (3,"three"), (5,"five"), (7,"seven"), (9, "nine"), (2,"two")]
for item in data:
heappush(heap, item)
sorted = []
while heap:
sorted.append(heappop(heap))
print sorted
data.sort()
print data == sorted``````

``````pq = []                         # list of entries arranged in a heap
entry_finder = {}               # mapping of tasks to entries
counter = itertools.count()     # unique sequence count

count = next(counter)
heappush(pq, entry)

entry[-1] = REMOVED

'Remove and return the lowest priority task. Raise KeyError if empty.'
while pq:
raise KeyError('pop from an empty priority queue')``````

``````>>> h = KeyHeap(sum)
>>> h.put([-1,1])
>>> h.put((-1,-2,-3))
>>> h.put({100})
>>> h.put([1,2,3])
>>> h.get()
(-1, -2, -3)
>>> h.get()
[-1, 1]
>>> h.get()
[1, 2, 3]
>>> h.get()
set([100])
>>> h.empty()
True
>>>
>>> k = KeyHeap(len)
>>> k.put('hello')
>>> k.put('')
>>> k.put('!')
>>> k.get()
'!'
>>> k.get()
'hello'
>>> k.get()
''``````

Python 2代碼

``````from Queue import PriorityQueue

class KeyHeap(PriorityQueue):
def __init__(self, key, maxsize=0):
PriorityQueue.__init__(self, maxsize)
self.key = key

def put(self, x):
PriorityQueue.put(self, (self.key(x), x))

def get(self):
return PriorityQueue.get(self)[1]``````

Python 3代碼

``````from queue import PriorityQueue

class KeyHeap(PriorityQueue):
def __init__(self, key, maxsize=0):
super().__init__(maxsize)
self.key = key

def put(self, x):
super().put((self.key(x), x))

def get(self):
return super().get()[1]``````

``````class PriorityQueueSet(object):

"""
Combined priority queue and set data structure.

Acts like a priority queue, except that its items are guaranteed to be
unique. Provides O(1) membership test, O(log N) insertion and O(log N)
removal of the smallest item.

Important: the items of this data structure must be both comparable and
hashable (i.e. must implement __cmp__ and __hash__). This is true of
Python's built-in objects, but you should implement those methods if you
want to use the data structure for custom objects.
"""

def __init__(self, items=[]):
"""
Create a new PriorityQueueSet.

Arguments:
items (list): An initial item list - it can be unsorted and
non-unique. The data structure will be created in O(N).
"""
self.set = dict((item, True) for item in items)
self.heap = self.set.keys()
heapq.heapify(self.heap)

def has_item(self, item):
"""Check if ``item`` exists in the queue."""
return item in self.set

def pop_smallest(self):
"""Remove and return the smallest item from the queue."""
smallest = heapq.heappop(self.heap)
del self.set[smallest]
return smallest