Python中heapq和PriorityQueue有什么区别？

Question

在Python中有一个内置的heapq算法，它提供了push、pop、nlargest、nsmallest等功能，可以应用于列表。然而，还有queue.PriorityQueue类似乎支持更多或更少相同的功能。它们的区别是什么，何时使用其中之一？

- yelsayed

Answer 1

Queue.PriorityQueue是一个线程安全的类，而heapq模块不提供线程安全保证。从Queue模块文档中可以看到：

Queue模块实现了多生产者、多消费者队列。它在多线程编程中特别有用，当信息必须在多个线程之间安全交换时。该模块中的Queue类实现了所有必需的锁定语义。它依赖于Python中线程支持的可用性；请参阅threading模块。

heapq模块不提供锁定，并且在标准的list对象上操作，这些对象不被设计成线程安全的。

实际上，PriorityQueue的实现在内部使用heapq来完成所有优先级工作，而基础的Queue类提供锁定以使其线程安全。有关详细信息，请参见源代码。

这使得heapq模块更快；没有锁定开销。此外，您可以自由地以不同的、新颖的方式使用各种heapq函数，而PriorityQueue仅提供简单的队列功能。

- Martijn Pieters

Answer 2

queue.PriorityQueue 是对heapq类的部分封装。

换句话说，queue.PriorityQueue 实际上是一个 heapq，只不过在队列模块中加入了一些重命名后的方法来使得使用heapq更加方便，就像普通队列一样。

在heapq中，你需要使用 heappush（） 方法添加新项和 heappop（） 方法删除一个项。这并不像队列那样直观易懂，因此queue.PriorityQueue 允许您使用常规队列方法，如put 和 get 来完成相同的操作。

heapq 有一些在queue.PriorityQueue中没有继承的特性，例如 heappushpop() 和 heapreplace() ，但您可能不太可能使用这些方法。如果您需要这些功能（就像我在我的当前项目中需要的一样），也许您应该使用heapq而不是queue.PriorityQueue。

此外，由于heapq专门为其目的而设计，因此它不是线程安全的（正如另一个回答中所注意到的那样）。

- Rory Daulton

Answer 3

是的，我找到了代码。很明显PriorityQueue使用了heapq。

class PriorityQueue(Queue):
    '''Variant of Queue that retrieves open entries in priority order (lowest first).

    Entries are typically tuples of the form:  (priority number, data).
    '''

    def _init(self, maxsize):
        self.queue = []

    def _qsize(self):
        return len(self.queue)

    def _put(self, item):
        heappush(self.queue, item)

    def _get(self):
        return heappop(self.queue)

- Eric Chow