Python的通用优先级队列
我需要在我的Python代码中使用优先级队列。 寻找有效的东西，我来到heapq 。 它看起来不错，但似乎只对整数指定。 我想它适用于任何具有比较运算符的对象，但是它没有指定它需要的比较运算符。
另外， heapq好像是用Python实现的，所以不是很快。
你知道Python中的优先级队列的快速实现吗？ 最好，我想队列是通用的（即对任何具有指定比较运算符的对象都适用）。
提前致谢
更新：
在heapq重新比较，我可以使用Charlie Martinbuild议的(priority, object) ，或者只是为我的对象实现__cmp__ 。
我仍然在寻找比heapq更快的东西。
嗯， Queue.PriorityQueue ？ 回想一下，Python不是强types的，所以你可以保存任何你喜欢的东西：只要创build一个（优先级，事物）的元组，然后设置。
我结束了为heapq实现一个包装，增加了维护队列的元素唯一的字典。 对于所有运营商来说，结果应该是非常有效的
class PriorityQueueSet(object): """ Combined priority queue and set data structure. Acts like a priority queue, except that its items are guaranteed to be unique. Provides O(1) membership test, O(log N) insertion and O(log N) removal of the smallest item. Important: the items of this data structure must be both comparable and hashable (ie must implement __cmp__ and __hash__). This is true of Python's built-in objects, but you should implement those methods if you want to use the data structure for custom objects. """ def __init__(self, items=[]): """ Create a new PriorityQueueSet. Arguments: items (list): An initial item list - it can be unsorted and non-unique. The data structure will be created in O(N). """ self.set = dict((item, True) for item in items) self.heap = self.set.keys() heapq.heapify(self.heap) def has_item(self, item): """Check if ``item`` exists in the queue.""" return item in self.set def pop_smallest(self): """Remove and return the smallest item from the queue.""" smallest = heapq.heappop(self.heap) del self.set[smallest] return smallest def add(self, item): """Add ``item`` to the queue if doesn't already exist.""" if item not in self.set: self.set[item] = True heapq.heappush(self.heap, item)
你看过heapq页面上的“Show Source”链接吗？ 有一个例子，使用一堆（int，char）元组列表作为优先级队列的一半。
我没有使用它，但你可以尝试PyHeap 。 这是用C写的，希望对你来说足够快。
你是积极的heapq / PriorityQueue会不够快？ 开始他们其中的一个可能是值得的，然后分析看看它是否真的是你的performance瓶颈。
您可以将heapq用于非整数元素（元组）
from heapq import * heap = [] data = [(10,"ten"), (3,"three"), (5,"five"), (7,"seven"), (9, "nine"), (2,"two")] for item in data: heappush(heap, item) sorted = [] while heap: sorted.append(heappop(heap)) print sorted data.sort() print data == sorted
这是有效的，适用于string或任何types的input – 🙂
pq = [] # list of entries arranged in a heap entry_finder = {} # mapping of tasks to entries REMOVED = '<removed-task>' # placeholder for a removed task counter = itertools.count() # unique sequence count def add_task(task, priority=0): 'Add a new task or update the priority of an existing task' if task in entry_finder: remove_task(task) count = next(counter) entry = [priority, count, task] entry_finder[task] = entry heappush(pq, entry) def remove_task(task): 'Mark an existing task as REMOVED. Raise KeyError if not found.' entry = entry_finder.pop(task) entry[-1] = REMOVED def pop_task(): 'Remove and return the lowest priority task. Raise KeyError if empty.' while pq: priority, count, task = heappop(pq) if task is not REMOVED: del entry_finder[task] return task raise KeyError('pop from an empty priority queue')
参考： http : //docs.python.org/library/heapq.html
当使用优先级队列时，reduce-key对许多algorithm（Dijkstraalgorithm，A *，OPTICS）来说是一个必须具备的操作，我想知道为什么Python的内置优先级队列不支持它。 其他答案都不提供支持此function的解决scheme。
还支持减键操作的优先级队列是由Daniel Stutzbach的这个实现为Python 3.5完美的工作。
from heapdict import heapdict hd = heapdict() hd["two"] = 2 hd["one"] = 1 obj = hd.popitem() print("object:",obj[0]) print("priority:",obj[1]) # object: one # priority: 1
我在https://pypi.python.org/pypi/fibonacci-heap-mod有一个优先队列/斐波那契堆;
它不是很快（大的常数c on delete-min，它是O（c * logn））。 但是find-min，insert，reduce-key和merge都是O（1） – IOW，这很懒。
如果CPython的速度太慢，你可以尝试Pypy，Nuitka甚至CPython + Numba 🙂
我可以使用Charlie Martinbuild议的
(priority, object)，或者仅仅为我的对象实现__cmp__。
如果你想插入的对象按照一个特定的规则进行优先级sorting，我发现编写一个简单的接受键控函数的PriorityQueue子类非常有用。 您不必手动插入(priority, object)元组，并且处理感觉更自然。
所需行为的演示 ：
>>> h = KeyHeap(sum) >>> h.put([-1,1]) >>> h.put((-1,-2,-3)) >>> h.put({100}) >>> h.put([1,2,3]) >>> h.get() (-1, -2, -3) >>> h.get() [-1, 1] >>> h.get() [1, 2, 3] >>> h.get() set([100]) >>> h.empty() True >>> >>> k = KeyHeap(len) >>> k.put('hello') >>> k.put('stackoverflow') >>> k.put('!') >>> k.get() '!' >>> k.get() 'hello' >>> k.get() 'stackoverflow'
Python 2代码
from Queue import PriorityQueue class KeyHeap(PriorityQueue): def __init__(self, key, maxsize=0): PriorityQueue.__init__(self, maxsize) self.key = key def put(self, x): PriorityQueue.put(self, (self.key(x), x)) def get(self): return PriorityQueue.get(self)[1]
Python 3代码
from queue import PriorityQueue class KeyHeap(PriorityQueue): def __init__(self, key, maxsize=0): super().__init__(maxsize) self.key = key def put(self, x): super().put((self.key(x), x)) def get(self): return super().get()[1]
很显然，如果你尝试插入一个key函数无法处理的对象，那么调用put会（并且应该）会引发一个错误。
