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

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
 1
 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).

15 comments

Brian Gladman 12 years, 1 month ago  # | flag

This code fails when I try it because it uses iteritems on line 24 but the class does not implement this.

Matteo Dell'Amico 12 years, 1 month ago  # | flag

It is a Python 2.x recipe. I guess you're using Python 3.x, where iteritems is called 'items'.

Brian Gladman 12 years, 1 month ago  # | flag

Thanks,

I hadn't realised that the name had changed between 2 and 3 - I'll check this out.

Brian

Brian Gladman 12 years, 1 month ago  # | flag

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,

 Brian
Matteo Dell'Amico 12 years, 1 month ago  # | flag

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

John Steedman 11 years, 8 months ago  # | flag

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):

# Pasted from :
# http://code.activestate.com/recipes/117228-priority-dictionary/

def __iter__(self):
    '''Create destructive sorted iterator of priorityDictionary.
    '''

    def iterfn():
        while len(self) > 0:
            x = self.smallest()
            yield x
            del self[x]
    return iterfn()
John Steedman 11 years, 8 months ago  # | flag

Brian Eppstein? I think I mean David Eppstein, sorry.

Matteo Dell'Amico 11 years, 8 months ago  # | flag

John,

I don't understand what's currently wrong with the sorted_iter() destructive method in my implementation.

John Sullivan 11 years, 3 months ago  # | flag

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

Matteo Dell'Amico 11 years, 3 months ago  # | flag

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.

John Sullivan 11 years, 3 months ago  # | flag

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.

Matteo Dell'Amico 11 years, 3 months ago  # | flag
John Sullivan 11 years, 3 months ago  # | flag

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

Matteo Dell'Amico 11 years, 3 months ago  # | flag

Great! It's always good to see that what I've been doing is useful!

Grant Jenks 9 years, 7 months ago  # | flag

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.