python - 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 使用 binary heap包含项目。

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

参见 https://github.com/python/cpython/blob/2.7/Lib/Queue.py和 https://docs.python.org/2/library/heapq.html了解详情。