#Python priority queue with tuples code#

Threading.Thread(target=worker_queue_creator, args=(Q,)), # create threads to consume and display the queue SleepE.wait(timeout=0.4) # quickly consume jobs Pre_q_str = str(q) # see what the Deque looks like before before pop SleepE.wait(timeout=1) # wait a moment to mock startup ''' daemon thread which consumes queue forever ''' # wait while the consumer worker processes these before exiting # one more important job before ending worker Q.append('high job 1') # add an important jobįor index in range(3, 3+3): # add a few more jobs SleepE = threading.Event() # use wait method for sleeping threadįor index in range(3): # start with a few jobs any unbounded collection will eventually run your system out of memory if input rate exceeds consumption.setting a length will let it push elements out of either end, not just off the left, unlike queue instances, which block or raise queue.Full.significantly faster than queue.PriorityQueue (see sketchy testing below).allows peeking arbitrary elements (indexable and iterable without popping, while queue instances can only be popped).append()īoth queue and deque instances have threadsafe push/pop methods appendleft(), and inserting your higher-priority entries at the right. If you only have a single 'higher priority' level rather than arbitrarily many as supported by queue.PriorityQueue, you can efficiently use a que for this by inserting normal jobs at the left. H = OrderedList(key=lambda x: x.priority) It can handle tuples like (priority, value) by default but you can also customize it like this: class Val(object): Return super(OrderedList, self)._getitem_(i) Return super(OrderedList, self).pop(i)įor x in super(OrderedList, self)._iter_():

Super(OrderedList, self).insert(i, (self.key(x), x)) Super(OrderedList, self).append((self.key(x), x)) pop(0)ĭef _init_(self, iterable=None, key=None): If you want MinQueue like functionality use positive values. If you want MaxQueue like functionality use negative values. '''Keep a list sorted as you append or extend itĪn ordered list, this sorts items from smallest to largest using key, so

#Python priority queue with tuples code#

If you want to keep an entire list ordered, not just the top value, I've used some variation of this code in multiple projects, it's a drop in replacement for the standard list class with a similar api: import bisect Obviously, calling put will (and should!) raise an error if you try to insert an object which your key-function cannot process. Python 3 code from queue import PriorityQueue PriorityQueue.put(self, (self.key(x), x)) Python 2 code from Queue import PriorityQueue You won't have to insert (priority, object) tuples manually and the handling feels more natural.ĭemo of the desired behavior: > h = KeyHeap(sum) If you want inserted objects to be prioritized by a specific rule, I found it very helpful to write a simple subclass of PriorityQueue which accepts a key-function. I can either use a (priority, object) as Charlie Martin suggests, or just implement _cmp_ for my object. '''Add ``item`` to the queue if doesn't already exist.''' '''Remove and return the smallest item from the queue.''' '''Check if ``item`` exists in the queue.''' The data structure will be created in O(N). Items (list): An initial item list - it can be unsorted and Want to use the data structure for custom objects. Python's built-in objects, but you should implement those methods if you Important: the items of this data structure must be both comparable and Provides O(1) membership test, O(log N) insertion and O(log N) The result should be quite efficient for all operators: class PriorityQueueSet(object):Ĭombined priority queue and set data structure.Īcts like a priority queue, except that its items are guaranteed to be I ended up implementing a wrapper for heapq, adding a dict for maintaining the queue's elements unique.