Priority Queue Using List
Priority Queue is a data structure that stores elements along with their priority. The element with the highest priority is dequeued first. In this implementation, we'll use a list to store the elements, and each element will be a tuple of the form (priority, value). The priority values determine the order in which elements are dequeued.
Here's the Python code for Priority Queue using a list:
class PriorityQueue:
def __init__(self):
self.queue = []
def is_empty(self):
return len(self.queue) == 0
def enqueue(self, priority, value):
# Append the element as a tuple (priority, value) to the list
self.queue.append((priority, value))
def dequeue(self):
if self.is_empty():
return None
# Sort the list in reverse order based on priority (higher priority first)
self.queue.sort(reverse=True)
# Dequeue the element with the highest priority (first element in the sorted list)
_, value = self.queue.pop(0)
return value
# Test the PriorityQueue implementation
pq = PriorityQueue()
pq.enqueue(3, 'Task 1')
pq.enqueue(1, 'Task 2')
pq.enqueue(2, 'Task 3')
print(pq.dequeue()) # Output: 'Task 2'
print(pq.dequeue()) # Output: 'Task 3'
print(pq.dequeue()) # Output: 'Task 1'
print(pq.dequeue()) # Output: None (queue is empty)
In the above code, we define the PriorityQueue class. The __init__ method initializes an empty list as the queue. The is_empty method checks if the queue is empty by checking the length of the list.
The enqueue method takes a priority and a value as arguments. It appends a tuple (priority, value) to the list, representing an element in the priority queue.
The dequeue method removes and returns the element with the highest priority. First, it checks if the queue is empty. Then, it sorts the list in reverse order based on priority, ensuring that higher priority elements come first. Finally, it pops and returns the value of the first element in the sorted list.
To test the implementation, we create a PriorityQueue object, enqueue three tasks with different priorities, and dequeue them one by one. The expected output is the values of the tasks in the order of their priorities.
The time complexity of this implementation is O(n log n) for enqueue and O(1) for dequeue. Enqueueing involves appending an element to the list, which takes constant time. However, the dequeue operation requires sorting the list, which has a time complexity of O(n log n) in the worst case, where n is the number of elements in the queue. The space complexity is O(n) since the list stores all the elements.
Let's solve a question using the Priority Queue implemented using a list. One such question is "Merge k Sorted Lists," where we need to merge k sorted linked lists into one sorted list.
Here's the code:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_k_lists(lists):
pq = PriorityQueue()
# Add the first node of each linked list to the priority queue
for node in lists:
if node:
pq.enqueue(node.val, node)
# Create a dummy node as the starting point of the merged list
dummy = ListNode()
curr = dummy
# Iterate until the priority queue is empty
while not pq.is_empty():
# Dequeue the node with the smallest value
_, node = pq.dequeue()
curr.next = node
curr = curr.next
# Move to the next node in the linked list
if node.next:
pq.enqueue(node.next.val, node.next)
return dummy.next
# Test the merge_k_lists function
# Create example linked lists
list1 = ListNode(1, ListNode(4, ListNode(5)))
list2 = ListNode(1, ListNode(3, ListNode(4)))
list3 = ListNode(2, ListNode(6))
# Merge the lists
result = merge_k_lists([list1, list2, list3])
# Print the merged list
while result:
print(result.val, end=' ')
result = result.next
# Output: 1 1 2 3 4 4 5 6
In this code, we define the ListNode class to represent a node in a linked list. The merge_k_lists function takes a list of linked lists as input and returns the merged list.
We create an instance of the PriorityQueue and add the first node of each linked list to the priority queue. The nodes are enqueued with their values as priorities. This allows us to maintain the order of the nodes based on their values.
We then create a dummy node as the starting point of the merged list. We iterate until the priority queue is empty. In each iteration, we dequeue the node with the smallest value from the priority queue, append it to the merged list, and move to the next node in the linked list. If the next node exists, we enqueue it with its value as the priority.
Finally, we return the next node of the dummy node, which represents the merged list.
The time complexity of this solution is O(N log K), where N is the total number of nodes across all linked lists and K is the number of linked lists. The enqueue operation takes O(log K) time, and we perform it for each node in the linked lists. The dequeue operation takes O(1) time, and we perform it for each node in the merged list. The space complexity is O(K), as we store up to K nodes in the priority queue.
Let's solve another question using the Priority Queue implemented using a list. One such question is "Kth Largest Element in an Array," where we need to find the kth largest element in an unsorted array.
Here's the code:
class PriorityQueue:
def __init__(self):
self.heap = []
def enqueue(self, val):
self.heap.append(val)
self.heapify_up(len(self.heap) - 1)
def dequeue(self):
if not self.is_empty():
self.swap(0, len(self.heap) - 1)
val = self.heap.pop()
self.heapify_down(0)
return val
def heapify_up(self, idx):
parent = (idx - 1) // 2
while idx > 0 and self.heap[parent] < self.heap[idx]:
self.swap(parent, idx)
idx = parent
parent = (idx - 1) // 2
def heapify_down(self, idx):
left_child = 2 * idx + 1
right_child = 2 * idx + 2
largest = idx
if left_child < len(self.heap) and self.heap[left_child] > self.heap[largest]:
largest = left_child
if right_child < len(self.heap) and self.heap[right_child] > self.heap[largest]:
largest = right_child
if largest != idx:
self.swap(idx, largest)
self.heapify_down(largest)
def is_empty(self):
return len(self.heap) == 0
def swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def find_kth_largest(nums, k):
pq = PriorityQueue()
# Add the first k elements to the priority queue
for i in range(k):
pq.enqueue(nums[i])
# Process the remaining elements
for i in range(k, len(nums)):
if nums[i] > pq.heap[0]:
pq.dequeue()
pq.enqueue(nums[i])
# Return the kth largest element
return pq.heap[0]
# Test the find_kth_largest function
nums = [3, 2, 1, 5, 6, 4]
k = 2
result = find_kth_largest(nums, k)
print(result) # Output: 5
In this code, we define the PriorityQueue class to implement a max heap using a list. The class provides methods for enqueue, dequeue, heapify operations, and checking if the heap is empty.
The find_kth_largest function takes an array of numbers and an integer k as input. It uses the priority queue to find the kth largest element in the array.
We initialize the priority queue and add the first k elements to it. This initializes the heap with the k largest elements. Then, we iterate through the remaining elements of the array. If an element is larger than the smallest element in the priority queue (the root of the max heap), we dequeue the smallest element and enqueue the new element. This ensures that the priority queue always contains the k largest elements.
Finally, we return the root of the priority queue, which represents the kth largest element.
The time complexity of this solution is O(N log K), where N is the length of the input array and K is the value of k. We perform k enqueue operations, each taking O(log K) time, and (N - k) dequeue operations, each taking O(log K) time. The space complexity is O(K), as we store up to K elements in the priority queue.