Является ли 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).

Подробнее см. https://github.com/python/cpython/blob/2.7/Lib/Queue.py и https://docs.python.org/2/library/heapq.html.

Answer 2

Это по порядку, но по порядку куча.PriorityQueue реализовано с помощью кучи.

q.queue - это простой список, но каждый раз, когда вы вставляете элемент, он выполняет сдвиг кучи.

Существует Сайт визуализации , который вы можете протестировать.И вы увидите, когда вы вставите (3, '3'), он меньше, чем его родительский узел (4, 'last'), поэтому они будут заменены.