How to Implement Priority Queues in Python
Introduction of Priority Queues
A Priority Queue is a data structure that manages a set of elements, each associated with a priority. The primary operations on a priority queue are inserting elements with their priority and extracting the element with the highest (or lowest) priority. Unlike traditional queues or stacks, a priority queue does not follow the first-in-first-out (FIFO) or last-in-first-out (LIFO) principles; rather, it prioritizes elements based on their assigned priorities.
What are heaps in Python?
In some situations we may need to find the minimum/maximum element among a collection of
elements. We can do this with the help of Priority Queue ADT. A priority queue ADT is a data
structure that supports the operations Insert and DeleteMin (which returns and removes the
minimum element) or DeleteMax (which returns and removes the maximum element).
Priority Queue ADT:
The following operations make priority queues an ADT.
Main Priority Queues Operations
- A priority queue is a container of elements, each having an associated key.
- Insert (key, data): Inserts data with key to the priority queue. Elements are ordered based on key.
- DeleteMin/DeleteMax: Remove and return the element with the smallest/largest key.
- GetMinimum/GetMaximum: Return the element with the smallest/largest key without deleting it.
Auxiliary Priority Queues Operations
- kth- Smallest/kth – Largest: Returns the kth-Smallest/kth –Largest key in priority queue.
- Size: Returns number of elements in priority queue.
- Heap Sort: Sorts the elements in the priority queue based on priority (key).
Types of Priority Queue:
Let’s understand the different types of priority queues because they define how elements are prioritized and dequeued based on their associated priority. There are two main types:
- Max Priority Queue
- The element with the highest priority is dequeued first.
- Commonly used when the most important or largest element must be processed first (e.g., job scheduling, bandwidth allocation).
- Min Priority Queue
- The element with the lowest priority is dequeued first.
- Useful in problems like finding the smallest element or in algorithms such as Dijkstra’s shortest path, where the minimum distance is always processed first.
Priority Queue Applications:
Priority queues have many applications – a few of them are listed below:
- Data compression: Huffman Coding algorithm
- Shortest path algorithms: Dijkstra’s algorithm
- Minimum spanning tree algorithms: Prim’s algorithm
- Event-driven simulation: customers in a line
- Selection problem: Finding k th- smallest element
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Implement Priority Queues in Python:
Implement Priority Queues in Python to efficiently manage elements based on their priority rather than their order of insertion. This data structure is widely used in tasks like scheduling, pathfinding, and resource management.
Using a List:
A simple implementation using a list where each element is a tuple of the form (priority, value).
# Implement Priority Queue using List (Approach A)
class PriorityQueue:
def __init__(self):
self.queue = []
def insert(self, item):
"""Insert an element into the queue"""
self.queue.append(item)
def delete(self):
"""Remove element with highest priority (max value)"""
if not self.queue:
return None
max_val = max(self.queue)
self.queue.remove(max_val)
return max_val
def display(self):
"""Display the queue"""
return self.queue
# Example usage
pq = PriorityQueue()
pq.insert(10)
pq.insert(5)
pq.insert(30)
pq.insert(20)
print("Queue after insertions:", pq.display())
print("Deleted element (highest priority):", pq.delete())
print("Queue after deletion:", pq.display())
Output:
Queue after insertions: [10, 5, 30, 20] Deleted element (highest priority): 30 Queue after deletion: [10, 5, 20]
- The priority queue is implemented using a simple Python list.
- insert() just appends elements to the end of the list.
- delete() finds the maximum element (highest priority) and removes it.
- display() shows the current state of the queue.
- This approach is simple but not very efficient for larger datasets.
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Insertion | O(1) | O(n) |
| Deletion | O(n) | O(n) |
| Display | O(n) | O(n) |
Using heapq Module (Binary Heap):
Python provides a heapq module that allows you to implement a binary heap-based priority queue.
import heapq
# Implement Priority Queue using heapq (Min Heap by default)
class PriorityQueue:
def __init__(self):
self.queue = []
def insert(self, item):
"""Insert element into heap"""
heapq.heappush(self.queue, item)
def delete(self):
"""Remove element with the smallest priority (min value)"""
if not self.queue:
return None
return heapq.heappop(self.queue)
def display(self):
"""Display current heap"""
return self.queue
# Example usage
pq = PriorityQueue()
pq.insert(10)
pq.insert(5)
pq.insert(30)
pq.insert(20)
print("Queue after insertions:", pq.display())
print("Deleted element (lowest priority):", pq.delete())
print("Queue after deletion:", pq.display())
Output:
Queue after insertions: [5, 10, 30, 20] Deleted element (lowest priority): 5 Queue after deletion: [10, 20, 30]
Explanation:
- Python’s heapq module provides a binary heap implementation.
- By default, heapq works as a Min Heap, so the smallest element has the highest priority.
- heappush() inserts an element into the heap efficiently.
- heappop() removes the smallest element from the heap.
- This approach is much faster than using lists for priority queues.
Time and Space Complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Insertion (heappush) | O(log n) | O(n) |
| Deletion (heappop) | O(log n) | O(n) |
| Display | O(n) | O(n) |
Using queue.PriorityQueue:
The queue module in Python includes a PriorityQueue class, which is a binary heap-based priority queue.
from queue import PriorityQueue
# Implement Priority Queue using queue.PriorityQueue
class MyPriorityQueue:
def __init__(self):
self.queue = PriorityQueue()
def insert(self, item):
"""Insert element into PriorityQueue"""
self.queue.put(item)
def delete(self):
"""Remove and return the element with the lowest value (highest priority)"""
if self.queue.empty():
return None
return self.queue.get()
def display(self):
"""Display elements (not direct, so convert to list)"""
temp_list = list(self.queue.queue)
return temp_list
# Example usage
pq = MyPriorityQueue()
pq.insert(10)
pq.insert(5)
pq.insert(30)
pq.insert(20)
print("Queue after insertions:", pq.display())
print("Deleted element (lowest priority):", pq.delete())
print("Queue after deletion:", pq.display())
Output:
Queue after insertions: [5, 10, 30, 20] Deleted element (lowest priority): 5 Queue after deletion: [10, 20, 30]
Explanation:
- Python’s queue.PriorityQueue is a thread-safe implementation of a priority queue.
- By default, it works like a Min Priority Queue (lowest value = highest priority).
- put() is used to insert an element, maintaining the priority internally.
- get() removes and returns the element with the smallest priority.
- Unlike heapq, this is synchronized and safe for multi-threaded applications.
Time and Space Complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Insertion (put) | O(log n) | O(n) |
| Deletion (get) | O(log n) | O(n) |
| Display (convert to list) | O(n) | O(n) |
To Wrap up with:
Priority queues are essential data structures in Python that allow efficient management of elements based on their priority. Whether implemented using a simple list, the heapq module, or queue.PriorityQueue, they provide flexible options for different performance needs.
These queues are widely used in scheduling tasks, shortest path algorithms, and resource management, making them a crucial tool for building efficient and optimized Python applications.
FAQs
A priority queue is a data structure where elements are processed based on priority rather than insertion order. Python provides heapq and queue.PriorityQueue to implement it.
Use heappush() with heapq or put() with queue.PriorityQueue to add elements along with their priority.
Use heappop() for heapq or get() for queue.PriorityQueue to extract the element with the highest or lowest priority.
Yes, heapq implements a min-heap by default; for a max-heap, you can invert priorities by storing negative values.
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment