You may have needed a priority queue with the ability to change the priorities of elements that were in the queue. This recipe solves this problem in an efficient way.
Python, 86 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 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | from heapq import heapify, heappush, heappop
class priority_dict(dict):
"""Dictionary that can be used as a priority queue.
Keys of the dictionary are items to be put into the queue, and values
are their respective priorities. All dictionary methods work as expected.
The advantage over a standard heapq-based priority queue is
that priorities of items can be efficiently updated (amortized O(1))
using code as 'thedict[item] = new_priority.'
The 'smallest' method can be used to return the object with lowest
priority, and 'pop_smallest' also removes it.
The 'sorted_iter' method provides a destructive sorted iterator.
"""
def __init__(self, *args, **kwargs):
super(priority_dict, self).__init__(*args, **kwargs)
self._rebuild_heap()
def _rebuild_heap(self):
self._heap = [(v, k) for k, v in self.iteritems()]
heapify(self._heap)
def smallest(self):
"""Return the item with the lowest priority.
Raises IndexError if the object is empty.
"""
heap = self._heap
v, k = heap[0]
while k not in self or self[k] != v:
heappop(heap)
v, k = heap[0]
return k
def pop_smallest(self):
"""Return the item with the lowest priority and remove it.
Raises IndexError if the object is empty.
"""
heap = self._heap
v, k = heappop(heap)
while k not in self or self[k] != v:
v, k = heappop(heap)
del self[k]
return k
def __setitem__(self, key, val):
# We are not going to remove the previous value from the heap,
# since this would have a cost O(n).
super(priority_dict, self).__setitem__(key, val)
if len(self._heap) < 2 * len(self):
heappush(self._heap, (val, key))
else:
# When the heap grows larger than 2 * len(self), we rebuild it
# from scratch to avoid wasting too much memory.
self._rebuild_heap()
def setdefault(self, key, val):
if key not in self:
self[key] = val
return val
return self[key]
def update(self, *args, **kwargs):
# Reimplementing dict.update is tricky -- see e.g.
# http://mail.python.org/pipermail/python-ideas/2007-May/000744.html
# We just rebuild the heap from scratch after passing to super.
super(priority_dict, self).update(*args, **kwargs)
self._rebuild_heap()
def sorted_iter(self):
"""Sorted iterator of the priority dictionary items.
Beware: this will destroy elements as they are returned.
"""
while self:
yield self.pop_smallest()
|
The priority queue is implemented as a dictionary, where keys are the items of the queue, and values are their priorities. Methods for obtaining the smallest item and doing sorted (destructive) iteration are provided.
To change an item's priority, it is sufficient to do thedict[item]=new_priority.
This recipe is an updated version (using the now available heapq module) of a 2002 recipe by David Eppstein (http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117228).
Tags: search
This code fails when I try it because it uses iteritems on line 24 but the class does not implement this.
It is a Python 2.x recipe. I guess you're using Python 3.x, where iteritems is called 'items'.
Thanks,
I hadn't realised that the name had changed between 2 and 3 - I'll check this out.
Brian
Yes, that fixed the initial problem. I was also assuming that your version was a direct replacement for David Eppstein's version when used with his Dijkstra shortest path code:
Dijkstra's algorithm for shortest paths David Eppstein, UC Irvine, 4 April 2002
But it fails with a runtime error:
builtins.RuntimeError: dictionary changed size during iteration
Thanks for your rapid response to my original query.
best regards,
In David Eppstein's recipe, __iter__ provides destructive iteration; here, __iter__ is dict's non-destructive iteration; it is sorted_iter that provides the kind of functionality you want. It should be easy to modify this recipe to do what you want.
If you're interested in shortest path implementation, you can also have a look at what networkx does: https://networkx.lanl.gov/trac/browser/networkx/networkx/algorithms/shortest_paths/weighted.py . It's particularly interesting, in my opinion, to look at bidirectional_dijkstra.
Cheers! matteo
Simple point but referring to the integration of Matteo's priority dict with Brian Eppstein's "Dijkstra" shortest path implementation [2], I found that introducing BE's __iter__ () function from [1] works well. BE's shortest path code requires that the destructive iterator does not destroy access via the current key until the very end of the current iteration (see [2]). For example, the following line must work even though the key/value pair at i will shortly be destroyed.
for i in myPD: print myPD [i]
[1] http://code.activestate.com/recipes/117228-priority-dictionary/ [2] http://code.activestate.com/recipes/119466-dijkstras-algorithm-for-shortest-paths/ (line 55/56)
This is what I have been testing.
class d_priority_dict (priority_dict):
Brian Eppstein? I think I mean David Eppstein, sorry.
John,
I don't understand what's currently wrong with the sorted_iter() destructive method in my implementation.
Matteo,
I would like to use this is my AGPLv3 licensed project but unfortunately anything that says "licensed under the PSF" here on ActiveState is licensed pretty ambiguously and legally I'm fairly sure anyone could make a case that it does not mean anything at all and the code is not freely licensed.
Would it be possible for you to relicense this recipe to remove the ambiguity? Possibly the unlicense if you don't have any rights you specifically want to keep? I do not know if you wish to use the unlicense but in case you do I have prepared an example of how to do it here. If you just copy and paste the contents of that gist (minus my little notice at the top) into another gist you will have "unlicensed" your code.
Have a great day,
John Sullivan
Dear John,
no problem on my part, but this is a modified version of David Eppstein's recipe, so I guess we need also his approval.
Thank you! I'm sorry for not noticing. Very good call.
David Eppstein has released his code under the unlicense. You can now relicense your code as you wish as you are the sole owner.
There you go: https://gist.github.com/4451520
Thank you very much! I've added your code into my project and you can see it here. I have not pushed the code that uses it yet as that will be a part of a fairly large commit, but I am using your code to help implement heartbeats between components of my system.
I hope you have a great day,
John Sullivan
Great! It's always good to see that what I've been doing is useful!
If you're looking for an API similar to that provided by this priority queue but you needed more functionality (e.g. accessing the min and max), 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.