Python的通用优先级队列

Question

我需要在Python代码中使用优先级队列.为了寻找有效的东西,我遇到了堆积.它看起来不错,但似乎只为整数指定.我认为它适用于具有比较运算符的任何对象,但它没有指定它需要哪些比较运算符.

此外,heapq似乎是用Python实现的,所以它并不快.

您是否了解Python中优先级队列的任何快速实现？最理想的情况是,我希望队列是通用的(即适用于具有指定比较运算符的任何对象).

提前致谢

更新:

重新比较heapq,我可以使用(priority, object)查理马丁建议的,或者只是__cmp__为我的对象实现.

我还在寻找比他更快的东西heapq.

Answer 1

嗯,Queue.PriorityQueue？回想一下,Python不是强类型的,所以你可以保存你喜欢的任何东西:只需要创建(优先级,事物)元组,然后设置它.

Answer 2

我最终实现了一个包装器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 3

当使用优先级队列时,reduce-key是许多算法必须具备的操作(Dijkstra算法,A*,OPTICS),我想知道为什么Python的内置优先级队列不支持它.其他答案都没有提供支持此功能的解决方案.

同时也支持减少按键操作的优先级队列为这个由丹尼尔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

Answer 4

您可以将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

Answer 5

我没用过它,但你可以试试PyHeap.它是用C语言写的,所以希望它对你来说足够快.

你是积极的heapq/PriorityQueue会不够快？它可能值得与其中一个开始,然后分析,看看它是否真的是你的性能瓶颈.

Answer 6

您是否查看了heapq页面上的"Show Source"链接？有一个例子比使用带有(int,char)元组列表的堆作为优先级队列的不到一半.