import heapq
class PriorityQueue(dict):
def __init__(self, _, f):
self.f = f
self.heap = []
def __delitem__(self, item):
super(PriorityQueue, self).__delitem__(item)
self.heap = [(v,k) for v,k in self.heap if k == item]
heapq.heapify(self.heap)
def pop(self):
_, smallest = heapq.heappop(self.heap)
super(PriorityQueue, self).__delitem__(smallest)
return smallest
def append(self, item):
self[item]=item
heapq.heappush(self.heap, (self.f(item), item))
Diff to Previous Revision
--- revision 2 2013-12-07 15:46:00
+++ revision 3 2013-12-08 07:33:57
@@ -7,9 +7,7 @@
def __delitem__(self, item):
super(PriorityQueue, self).__delitem__(item)
- removed = [i for i, (v,k) in enumerate(self.heap) if key == item]
- for i in removed:
- del self.heap[i]
+ self.heap = [(v,k) for v,k in self.heap if k == item]
heapq.heapify(self.heap)
def pop(self):
