Based on the interface defined in aima-python http://aima-python.googlecode.com/svn/trunk/utils.py
Yields better performance.
Python, 23 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | 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)
|
How does the performance compare to Python's own PriorityQueue?
Mark, I did not test python's implementation, since it does not support item deletion. Note also that python's version is synchronized.
Consider priority dict: it has more features and better performance (http://code.activestate.com/recipes/522995/)
Matteo, as it is stated in the description, this recipe has a specific goal: Fitting into aima-python implementation of A* seamlessly.
If you're looking for an API similar to that provided by a priority queue, check out the sortedcontainers module. It implements sorted list, sorted dict, and sorted set data types in pure-Python and is fast-as-C implementations (even faster!). Learn more about sortedcontainers, available on PyPI and github.