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

不应对优先级队列进行排序。优先级队列仅保证在您调用get()时会返回最高优先级的项目。

在内部，queue.PriorityQueue使用二进制堆来包含项目。

它不使用排序数组的原因是因为维护排序数组很昂贵。添加和删除项目将是O（n）操作。二进制堆执行那些O（log n）操作。