Python的通用优先级队列

Question

我需要在Python代码中使用优先级队列，并且：

• 我正在寻找优先级队列的任何快速实现
• 最理想的情况是，我希望队列是泛型的（即，对于具有指定比较运算符的任何对象都可以正常工作）。

我四处寻找有效率的东西，偶然发现了heapq，但是：

• 我正在寻找比用原生Python实现的heapq更快的东西，所以速度不快。
• 它看起来不错，但似乎只为整数指定。我想它适用于任何有比较运算符的对象，但是它没有指定它需要什么比较运算符。
• 更新：在heapq中重新比较，我可以像Charlie Martin建议的那样使用(priority, object)，或者只为我的对象实现__cmp__。

Answer 1

最后，我实现了heapq的包装，添加了一个dict来保持队列元素的唯一性。结果应该对所有操作员都非常有效：

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 (i.e. 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)

Answer 2

您可以使用Queue.PriorityQueue。

回想一下，Python不是强类型的，所以您可以保存任何您喜欢的内容：只需创建一个(priority, thing)元组就可以了。

Answer 3

当使用优先级队列时，decrease key是许多算法（Dijkstra的算法，a*，OPTICS）的必备操作，我想知道Python的内置优先级队列为什么不支持它。其他答案都没有提供支持此功能的解决方案。

支持reduce key操作的优先级队列是Daniel Stutzbach的this实现，它在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