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)