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

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)

5 comments

Mark Lawrence 10 years, 4 months ago  # | flag

How does the performance compare to Python's own PriorityQueue?

elazar (author) 10 years, 4 months ago  # | flag

Mark, I did not test python's implementation, since it does not support item deletion. Note also that python's version is synchronized.

Matteo Dell'Amico 10 years, 4 months ago  # | flag

Consider priority dict: it has more features and better performance (http://code.activestate.com/recipes/522995/)

elazar (author) 10 years, 4 months ago  # | flag

Matteo, as it is stated in the description, this recipe has a specific goal: Fitting into aima-python implementation of A* seamlessly.

Grant Jenks 9 years, 7 months ago  # | flag

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.