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:
pQueue.put(value)
The get command dequeues the highest priority elements from the queue.
Priority-object pairs can also be inserted into the queue. This way every task can be associated with a priority.
Time Complexity
Operation: Work-case Time complexity:
Insertion O(logn)
Deletion O(logn)
Top comments (0)