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?

Jim Mischel · Accepted Answer · 2018-05-31 03:39:06Z

11

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.

answered May 31, 2018 at 3:39

Jim Mischel

135k25 gold badges197 silver badges377 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Sraw · Accepted Answer · 2018-05-31 03:38:39Z

1

It is in order, but the order of heap. PriorityQueue is implemented by heap.

The q.queue is just a simple list, but every time you insert an element, it will do heap shift.

There is a visualization website which you can test. And you will see when you insert (3, '3'), it is smaller than its parent node (4, 'last'), so they will be exchanged.

answered May 31, 2018 at 3:38

Sraw

20.6k11 gold badges61 silver badges93 bronze badges

Collectives™ on Stack Overflow

Is Python's Queue.PriorityQueue not automatically sorted?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related