Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

python
priority queue
data structure
queue
heap

What is the Python priority queue?

Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Answers Code

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 ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Answers Code
Keep Exploring