Is Python's Queue.PriorityQueue not automatically sorted?

Question

I am new to using queues in Python and I recently started working with the PriorityQueue.

I was expecting that elements would be inserted in the queue according to the a priority number. That is, if I did something like:

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

I was expecting this output:

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

Instead I get:

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

However, if I get the elements out of the queue by something like:

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

I do get the output I would expect:

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

I was trying to debug something by printing the queue at some points and noticed the elements were not in the order I would expect. Unless I missed it, Queue's docs don't mention anything about sorting. Was I just wrong to expect it to be sorted? Could it be simply not be implemented that way for efficiency reasons?

Answer 1

A priority queue is not supposed to be sorted. The priority queue only guarantees that when you call get(), it returns you the highest priority item.

Internally, queue.PriorityQueue uses a binary heap to contain the items.

The reason it doesn't use a sorted array is because maintaining a sorted array is expensive. Adding and removing items would be O(n) operations. A binary heap makes those O(log n) operations.

See https://github.com/python/cpython/blob/2.7/Lib/Queue.py and https://docs.python.org/2/library/heapq.html for details.