Python的Queue.PriorityQueue不是自动排序的吗？

Question

我刚开始使用 Python 中的队列，最近开始使用 PriorityQueue。

我原以为元素会根据优先级编号插入队列中。也就是说，如果我做了类似的事情：

from Queue import PriorityQueue

q = PriorityQueue()
q.put((1, '1'))
q.put((4, 'last'))
q.put((2, '2'))
q.put((3, '3'))

print q.queue

我期待这个输出：

[(1, '1'), (2, '2'), (3, '3'), (4, 'last')].

相反，我得到：

[(1, '1'), (3, '3'), (2, '2'), (4, 'last')]

但是，如果我通过以下方式从队列中取出元素：

while not q.empty():
    item = q.get()
    print item

我确实得到了我期望的输出：

(1, '1')
(2, '2')
(3, '3')
(4, 'last')

我试图通过在某些点打印队列来调试某些内容，但发现元素的顺序不符合我的预期。除非我错过了，否则 Queue 的文档不会提及任何有关排序的内容。我只是错误地期望它被分类吗？出于效率原因，是否可以简单地不以这种方式实施？

Answer 1

是有序的，但是堆的顺序。 PriorityQueue是堆实现的。

q.queue只是一个简单的列表，但是每插入一个元素，它就会进行堆移位。

有一个 visualization website 您可以测试。并且你会看到当你插入(3, '3')时，它比它的父节点(4, 'last')小，所以它们会被交换

Answer 2

不应该对优先级队列进行排序。优先级队列只保证当你调用get()时，它returns你是最高优先级的项目。

在内部，queue.PriorityQueue 使用 binary heap 来包含项目。

它不使用排序数组的原因是维护排序数组的成本很高。添加和删除项目将是 O(n) 操作。二叉堆进行那些 O(log n) 操作。

Is Python's Queue.PriorityQueue not automatically sorted?