Based on the interface defined in aima-python http://aima-python.googlecode.com/svn/trunk/utils.py
Yields better performance.
Python, 23 lines
1 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)
Tags: artificial_intelligence, heap, heapq, priority_queue, queue
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.