At the moment, I am trying to write a priority queue in Python using the built in heapq library. However, I am stuck trying to get a handle on what Python does with the tie-breaking, I want to have a specific condition where I can dictate what happens with the tie-breaking instead of the heapq library that seems to almost pick something off the queue at random. Does anybody know of a way of rewriting the tie-breaking condition or would it be easier to build the priority queue from the ground up?
1
-
When you looked at the code, what did you find? Which class was it in? Which method? Did you try to subclass it to replace the method with something more to your liking?S.Lott– S.Lott2009-09-14 17:52:43 +00:00Commented Sep 14, 2009 at 17:52
Add a comment
|
1 Answer
heapq uses the intrinsic comparisons on queue items (__le__ and friends). The general way to work around this limit is the good old approach known as "decorate/undecorate" -- that's what we used to do in sorting, before the key= parameter was introduced there.
To put it simply, you enqueue and dequeue, not just the items you care about ("payload"), but rather the items "decorated" into tuples that start with the "keys" you need heapq to consider. So for example it would be normal to enqueue a tuple like (foo.x, time.time(), foo) if you want prioritization by the x attribute with ties broken by time of insertion in the queue -- of course when you de-queue you "undecorate", there by taking the [-1]th item of the tuple you get by de-queueing.
So, just put the "secondary keys" you need to be considered for "tie-breaking" in the "decorated" tuple you enqueue, AFTER the ones whose "ties" you want to break that way.
answered Sep 14, 2009 at 17:59
Alex Martelli
887k175 gold badges1.3k silver badges1.4k bronze badges