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

Recipe 578780 revision 5 

import heapq

class PriorityQueue(dict):
    def __init__(self, _, f):
        self.f = f
        self.heap = []
    
    def __delitem__(self, item):
        self._remove_from_dict(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)
        self._remove_from_dict(smallest)
        return smallest

    def append(self, item):
        self[item]=item
        heapq.heappush(self.heap, (self.f(item), item))

    def _remove_from_dict(self, item):
        super(PriorityQueue, self).__delitem__(item)

Diff to Previous Revision

--- revision 4 2013-12-08 07:35:32
+++ revision 5 2013-12-08 21:12:55
@@ -6,15 +6,18 @@
         self.heap = []
     
     def __delitem__(self, item):
-        super(PriorityQueue, self).__delitem__(item)
+        self._remove_from_dict(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)
+        self._remove_from_dict(smallest)
         return smallest
 
     def append(self, item):
         self[item]=item
         heapq.heappush(self.heap, (self.f(item), item))
+
+    def _remove_from_dict(self, item):
+        super(PriorityQueue, self).__delitem__(item)

History