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

Recipe 578780 revision 4 

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 3 2013-12-08 07:33:57
+++ revision 4 2013-12-08 07:35:32
@@ -7,7 +7,7 @@
     
     def __delitem__(self, item):
         super(PriorityQueue, self).__delitem__(item)
-        self.heap = [(v,k) for v,k in self.heap if k == item]
+        self.heap = [(v,k) for v,k in self.heap if k != item]
         heapq.heapify(self.heap)
     
     def pop(self):

History