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.
0 kommentar(er)
