Priority Queue Data Structure Unpacked : A task scheduler perspective
A priority queue is like a special to-do list where each task has its own level of importance. Unlike a regular to-do list, where tasks are done in the order they are added, a priority queue makes sure the most important task gets done first.
What's Inside a Priority Queue?
Adding Tasks (Enqueue):
When you add a task to a priority queue, you also say how important it is. The more important, the sooner it gets done.
Doing Tasks (Dequeue):
The priority queue takes care of doing the most important task first. It's like automatically picking the task with the highest priority.
Checking the Top Task(peek):
You can peek at the top task without actually doing it. This is useful when you want to see what's the most important thing right now.
Changing Importance:
If something becomes more urgent or less critical, you can change its priority in the queue.
Implementation Approaches:
Heap-based Priority Queue:
Heap Structure:
A binary heap is frequently used to implement a priority queue. It ensures that the element with the highest priority is at the root of the heap.
Time Complexity:
Insertion: O(log n)
Deletion: O(log n)
Space Complexity:
O(n)
pimport heapq
class HeapPriorityQueue:
def __init__(self):
self.heap = []
def insert(self, element, priority):
"""
Insert an element into the heap-based priority queue.
Time Complexity: O(log n)
"""
heapq.heappush(self.heap, (priority, element))
def delete_max(self):
"""
Delete the element with the highest priority from the heap-based priority queue.
Time Complexity: O(log n)
"""
if self.heap:
return heapq.heappop(self.heap)
else:
return None
def peek_max(self):
"""
Peek at the element with the highest priority without removing it.
Time Complexity: O(1)
"""
if self.heap:
return self.heap[0]
else:
return None
def change_priority(self, element, new_priority):
"""
Change the priority of an element in the heap-based priority queue.
Time Complexity: O(n) - Inefficient, better approaches are possible.
"""
# Remove the element with the old priority
self.heap = [(priority, elem) for priority, elem in self.heap if elem != element]
# Insert the element with the new priority
self.insert(element, new_priority)
# Example Usage
heap_priority_queue = HeapPriorityQueue()
heap_priority_queue.insert("Task A", 3)
heap_priority_queue.insert("Task B", 1)
heap_priority_queue.insert("Task C", 2)
print("Heap-based Priority Queue (Before):", heap_priority_queue.heap)
# Change the priority of "Task B" to 4
heap_priority_queue.change_priority("Task B", 4)
print("Heap-based Priority Queue (After):", heap_priority_queue.heap)
2.Array-based Priority Queue:
Sorted Array:
Elements are stored in a sorted manner based on their priorities.
Time Complexity:
Insertion: O(n)
Deletion: O(1)
Space Complexity:
O(n)
class ArrayPriorityQueue:
def __init__(self):
self.array = []
def insert(self, element, priority):
"""
Insert an element into the array-based priority queue.
Time Complexity: O(n)
"""
self.array.append((element, priority))
self.array.sort(key=lambda x: x[1]) # Sort based on priority
def delete_max(self):
"""
Delete the element with the highest priority from the array-based priority queue.
Time Complexity: O(1)
"""
if self.array:
return self.array.pop()
else:
return None
def peek_max(self):
"""
Peek at the element with the highest priority without removing it.
Time Complexity: O(1)
"""
if self.array:
return self.array[-1]
else:
return None
def change_priority(self, element, new_priority):
"""
Change the priority of an element in the array-based priority queue.
Time Complexity: O(n)
"""
for i in range(len(self.array)):
if self.array[i][0] == element:
# Update the priority of the element
self.array[i] = (element, new_priority)
# Re-sort the array based on priorities
self.array.sort(key=lambda x: x[1])
return
# Example Usage
array_priority_queue = ArrayPriorityQueue()
array_priority_queue.insert("Task A", 3)
array_priority_queue.insert("Task B", 1)
array_priority_queue.insert("Task C", 2)
print("Array-based Priority Queue (Before):", array_priority_queue.array)
# Change the priority of "Task B" to 4
array_priority_queue.change_priority("Task B", 4)
print("Array-based Priority Queue (After):", array_priority_queue.array)
Where You See Priority Queues
Getting Things Done:
It's like managing your tasks with a sense of priority – doing the most important things first.
Video Games:
In some games, characters or actions are prioritized based on their importance in the game's logic.
Emergency Rooms:
Patients are treated based on the urgency of their condition – just like a priority queue
Real-world Applications
Understanding the synergy between Priority Queues and task schedulers is crucial for designing efficient algorithms. Real-world applications include:
Operating Systems: Managing processes and system resources.
Job Scheduling: Prioritizing and scheduling jobs based on criticality.
Networking: Handling data packets with varying levels of priority during transmission.
Dijkstra's Shortest Path Algorithm:
Network Routing: Priority queues are integral to algorithms like Dijkstra's, which is used for finding the shortest path in network routing.
In a nutshell
A priority queue is like having a smart to-do list that always helps you focus on the most important things first – a helpful concept in the busy world of computing and problem-solving.
