Priority Queues in DSA
Priority queues in DSA govern a group of prioritised objects, unlike standard queues. A Priority Queue permits random additions but deletes or accesses the most important item first. In contrast, a traditional queue processes items in order of receipt. Most important items take precedence over longest-standing ones, which may not be eliminated next.
For example, if devoted patrons are given preference in a movie theatre based on their loyalty points, the ticket line turns into a priority line where loyalty serves as the key or priority. In a similar vein, an operating system may schedule tasks with equal priority using priority queues in dsa.
Types of Priority Queues
Based on their ordering, priority queues in DSA can be broadly divided into two types:
Max Priority Queue: An element with the highest priority value is regarded as the highest priority and is eliminated first in a max priority queue, which arranges data in declining order of priority. A Max Priority Queue places data in declining order of priority. A priority queue uses a specific comparison to arrange items, with the highest priority item usually having the greatest value (or key). This indicates that the highest priority or largest key element will always be removed from a Max Priority Queue.
Min Priority Queue: The element with the lowest priority value is regarded as the greatest priority and is eliminated first in a min priority queue, which arranges data according to priority. A Min Priority Queue method is frequently assumed unless otherwise noted. A Min Priority Queue is a specific abstract data structure that ranks its members by priority, unlike a FIFO queue. The element with the shortest key (or greatest priority in a “minimum-first” context) is eliminated or accessed first in a min priority queue.
Operations Associated with Priority Queues
Basic operations are supported via priority queues in DSA , which are usually represented by key-value pairs in which the priority is determined by the key. Typical techniques consist of:
- Add(k, v) / insert(node) adds k and v to the priority queue. Priority determines how data is kept.
- Remove min() and delete() yield the lowest-key item (highest priority). If the queue is empty, an error occurs.
A reference to the item with the minimum key is returned by min(), first(), and peek() without the key being removed. This operation is comparable to the first method of a queue or the top method of a stack. - is_empty(): Gives back True if there are no entries in the priority queue.
- The number of entries in the priority queue is returned by len() / size().
Priority Queues and Heaps
A popular and effective data structure for setting up priority queues in DSA is heaps. The reason for this is that heaps allow for efficient insertions and removals by offering a good compromise between lists that are completely unsorted and lists that are flawlessly sorted.
Heap-Order Property
All heap nodes save the root have keys greater than their parents, according to heap-order. The lowest (or maximum, in a max-heap) key is always at the root of the tree, making the highest priority item easy to find. Heap data structures, a form of binary tree used to store objects, have a fundamental relational feature called the Heap-Order feature. This property orders keys in the tree by parent-child connection. In a “min heap,” the key stored at every location in the tree other than the root must be greater than or equal to its parent. Thus, a min heap’s smallest key is always at the root. In contrast, in a “max heap,” the parent node’s value exceeds its children’s.
Structural Property:
structural element Heaps are entire binary trees. It appears that all tree levels except the last are filled left to right. Because elements can be easily mapped to array indices, this structural feature enables an effective array-based representation of the heap. Data structures have inherent shapes based on their structural properties. In a heap, the structural property describes the binary tree’s form, whereas the relational property controls key storage.
A binary search tree’s structural characteristic assures that an in-order traversal of its members results in a non-decreasing order. The “Height-Balance Property” in AVL trees demands that every node’s children’s heights differ by no more than one.
The majority of priority queue operations have logarithmic time complexity when implemented with a heap.
Insertion (add): To preserve the whole binary tree property, a new item is inserted to the heap’s next accessible place. An “up-heap bubbling” procedure is then carried out. This entails advancing the item upwards until its suitable location is identified by continually comparing the newly inserted item with its parent and switching them if the heap-order property is broken. This has an O(log n) time complexity in the worst scenario, requiring swaps equivalent to the tree’s height.
Removal (remove min): The minimum key, or element at the root, is eliminated. The final piece in the heap is shifted to the root’s location in order to preserve the heap’s structure. A process known as “down-heap bubbling” is then started. If the heap-order property is broken, this entails comparing the new root with its offspring and replacing it with the smaller of its offspring (for a min-heap). Until the property is restored, this procedure keeps going downhill. The temporal complexity of this procedure is O(log n) as well.
Accessing Minimum (min/peek): It takes O(1) time to retrieve the minimum element because the heap-order attribute ensures that it is always at the root.
Example Python List-based Priority Queue
It shows how to create a priority queue using a Python list that preserves priority during insertion, even though heaps are the industry standard for effective priority queue implementations. Insert can be O(N) in the worst case because it iterates over the list to find the correct sorted location, whereas delete and show are O(1). The heapq module in Python’s standard library allows heappop and O(log n) heappush operations on a Python list as a min-heap.
A list and priority-based inserts create a basic priority queue in Python:
Example:
# class for Node with data and priority
class Node:
def _init_(self, info, priority):
self.info = info
self.priority = priority
# class for Priority queue
class PriorityQueue:
def _init_(self):
self.queue = list()
def size(self):
return len(self.queue)
def insert(self, node):
# If queue is empty, simply add the new node
if self.size() == 0:
self.queue.append(node)
else:
# Traverse the queue to find the right place for the new node
# This ensures elements are kept in sorted order by priority (min-priority queue)
inserted = False
for x in range(self.size()):
# If new node's priority is less than the current node's priority,
# insert it before the current node and break the loop.
if node.priority < self.queue[x].priority:
self.queue.insert(x, node)
inserted = True
break
# If the node was not inserted (i.e., its priority is higher than or equal to all existing nodes),
# add it to the end of the queue.
if not inserted:
self.queue.append(node)
def delete(self):
# Remove the first node (element with least priority value, i.e., highest priority)
if self.size() == 0:
return None
return self.queue.pop(0)
def show(self):
# Prints all elements in the priority queue
for x in self.queue:
print(f"{x.info} - {x.priority}")
# Example Usage:
print("Initializing Priority Queue...")
pQueue = PriorityQueue()
node1 = Node("C", 3)
node2 = Node("B", 2)
node3 = Node("A", 1)
node4 = Node("Z", 26)
node5 = Node("Y", 25)
node6 = Node("L", 12)
node7 = Node("D", 4)
print("\nInserting elements:")
pQueue.insert(node1)
pQueue.insert(node2)
pQueue.insert(node3)
pQueue.insert(node4)
pQueue.insert(node5)
pQueue.insert(node6)
pQueue.insert(node7)
pQueue.show()
print("\n")
print("Deleting element (highest priority):")
deleted_node = pQueue.delete()
if deleted_node:
print(f"Deleted: {deleted_node.info} - {deleted_node.priority}")
pQueue.show()
print("\n")
print("Deleting another element:")
deleted_node = pQueue.delete()
if deleted_node:
print(f"Deleted: {deleted_node.info} - {deleted_node.priority}")
pQueue.show()Output:
Initializing Priority Queue...
Inserting elements:
A - 1
B - 2
C - 3
D - 4
L - 12
Y - 25
Z - 26
Deleting element (highest priority):
Deleted: A - 1
B - 2
C - 3
D - 4
L - 12
Y - 25
Z - 26
Deleting another element:
Deleted: B - 2
C - 3
D - 4
L - 12
Y - 25
Z - 26The item with the lowest priority is always at the front and can be retrieved or deleted in O(1) time since the Priority Queue keeps objects’ order by priority (Node.priority) at entry. Our worst-case insertion approach is O(n) since it searches the list for the proper spot. The Python heapq module improves efficiency (insertion and deletion take O(log n)).