Welcome, guest | Sign In | My Account | Store | Cart

Recipe 578780 revision 2 

import heapq

class PriorityQueue(dict):
    def __init__(self, _, f):
        self.f = f
        self.heap = []
    
    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]
        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 1 2013-12-05 23:58:42
+++ revision 2 2013-12-07 15:46:00
@@ -7,7 +7,9 @@
     
     def __delitem__(self, item):
         super(PriorityQueue, self).__delitem__(item)
-        del self.heap[self.heap.index(item)]
+        removed = [i for i, (v,k) in enumerate(self.heap) if key == item]
+        for i in removed:
+            del self.heap[i]
         heapq.heapify(self.heap)
     
     def pop(self):

History