DEV Community


Posted on

What is the Python priority queue?

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.

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:

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

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

Image description

Time Complexity

Operation: Work-case Time complexity:
Insertion O(logn)
Deletion O(logn)

Discussion (0)