Trusted answers to developer questions

What is the Python priority queue?

Get the Learn to Code Starter Pack

Break into tech with the logic & computer science skills you’d learn in a bootcamp or university — at a fraction of the cost. Educative's hand-on curriculum is perfect for new learners hoping to launch a career.

The priority queue is an advanced type of the queue data structure. Instead of dequeuing the oldest element, a priority queue sorts and dequeues elements based on their priorities.

Priority queues are used to handle scheduling problems where some tasks are prioritized over others.

The queue.PriorityQueue Class

Python provides a built-in implementation of the priority queue data structure.

Since the queue.PriorityQueue class needs to maintain the order of its elements, a sorting mechanism is required every time a new element is enqueued.

Python solves this by using a binary heap to implement the priority queue.

1 of 15

The Python priority queue is built on the heapq module, which is basically a binary heap.

For insertion, the priority queue uses the put function in the following way:

    pQueue.put(value)

The get command dequeues the highest priority elements from the queue.

from queue import PriorityQueue
q = PriorityQueue()
q.put(4)
q.put(2)
q.put(5)
q.put(1)
q.put(3)
while not q.empty():
next_item = q.get()
print(next_item)

Priority-object pairs can also be inserted into the queue. This way every task can be associated with a priority.

from queue import PriorityQueue
q = PriorityQueue()
q.put((4, 'Read'))
q.put((2, 'Play'))
q.put((5, 'Write'))
q.put((1, 'Code'))
q.put((3, 'Study'))
while not q.empty():
next_item = q.get()
print(next_item)

Time Complexity

Operation Worst-case Time Complexity
Insertion O(logn)
Deletion O(logn)

RELATED TAGS

python
priority queue
data structure
queue
heap
Copyright ©2024 Educative, Inc. All rights reserved
Did you find this helpful?