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).
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
Python priority queue methods:
A priority queue is a data structure that maintains a set of elements, each associated with a priority, and allows efficient access to and removal of the element with the highest (or lowest) priority. Here are some examples of use cases where priority queues are particularly useful:
- Dijkstra’s Shortest Path Algorithm:In graph algorithms like Dijkstra’s, a priority queue is used to efficiently select and process nodes with the minimum distance during the traversal.
- A Search Algorithm:*Similar to Dijkstra’s algorithm, the A* search algorithm uses a priority queue to explore paths in order of increasing cost, combining the cost to reach a node and a heuristic estimate of the cost from that node to the goal.
- Huffman Coding:Huffman coding, used in data compression, involves assigning variable-length codes to input characters based on their frequencies. Priority queues help in building the Huffman tree by repeatedly merging the nodes with the lowest frequencies.
- Job Scheduling:In task scheduling scenarios, jobs often have different priorities or deadlines. A priority queue can be used to efficiently schedule and execute jobs based on their priority or deadline.
- Operating System Process Scheduling:Operating systems use priority queues to manage the execution of processes. Processes with higher priority are given preference in execution, ensuring that critical tasks are handled promptly.
- Load Balancing:Priority queues can be employed in load balancing systems to manage tasks or requests based on their priority or urgency, ensuring that important tasks are handled first.
- Distributed Systems:In distributed systems, messages or tasks may have different priorities. Priority queues help in managing the order of processing tasks in a distributed environment.
- Event-driven Simulation:Simulations often involve events that occur at different times and have different priorities. Priority queues can be used to maintain and process events in the order of their occurrence.
- Data Compression:In algorithms like Huffman coding, where symbols need to be encoded based on their frequencies, priority queues are used to efficiently process and merge symbols.
- Networking Protocols:Some networking protocols involve processing packets with different priorities. Priority queues can be employed to handle packets based on their priority levels, ensuring timely processing of critical information.
Priority Queue Implementations:
Using a List:A simple implementation using a list where each element is a tuple of the form (priority, value).
class PriorityQueueList:
def __init__(self):
self.elements = []
def enqueue(self, priority, value):
self.elements.append((priority, value))
self.elements.sort(reverse=True) # Sorting in descending order based on priority
def dequeue(self):
if not self.is_empty():
return self.elements.pop()
def is_empty(self):
return len(self.elements) == 0
Using heapq Module (Binary Heap):Python provides a heapq module that allows you to implement a binary heap-based priority queue.
import heapq
class PriorityQueueBinaryHeap:
def __init__(self):
self.elements = []
def enqueue(self, priority, value):
heapq.heappush(self.elements, (priority, value))
def dequeue(self):
if not self.is_empty():
return heapq.heappop(self.elements)
def is_empty(self):
return len(self.elements) == 0
Using queue.PriorityQueue:The queue module in Python includes a PriorityQueue class, which is a binary heap-based priority queue.
from queue import PriorityQueue
class PriorityQueueModule:
def __init__(self):
self.elements = PriorityQueue()
def enqueue(self, priority, value):
self.elements.put((priority, value))
def dequeue(self):
if not self.is_empty():
return self.elements.get()
def is_empty(self):
return self.elements.empty()
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
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