A Priority Queue is a special collection of elements that are arranged in order of decreasing priority of elements. It allows element deletion in front of queue. Insertions are not done at rear like a general queue. It is allowed at a place satisfying the sequence of priorities of the queue elements. In this post we will discuss how to create Priority Queue Python.
Priority Queue Basics
- Priority queue stores all the elements according to the decreasing priorities of elements. So, every node of the priority queue will store an additional field “Priority”. This is a numeric value defining how important the element is in terms of its deletion/processing.
- To insert an element, the priority of new
element is compared with priority of existing elements starting from the first
element.
- If the new element is of highest priority it is added at the beginning of the Priority Queue.
- If the new element is of lowest priority it is added at the end of the Priority Queue.
- If the new element has priority somewhere in between, its location of insertion is found and then it is inserted.
- The element with highest priority must be processed first. Since the first element has highest priority, it is deleted first. The elements with lower priorities will be deleted later.
- The deletion in a Priority Queue is like a general queue with Front and Rear pointers.
- Insertion in a Priority Queue is like insertion in a sorted linked list. It is not done at the rear of the queue. So, Priority queue can be created without Rear Pointer.
Implementation of Priority Queue Python
In the code presented here, the Priority Queue is implemented using a Python Linked List.
Each node is defined as Node(Data, Priority, Link(to next node))
Deletion
- Store data part of first node in item variable.
- Returning it to be processed or printed.
- Front Pointer is updated with address of next node stored in link part of first node.
Insertion
- Traversing through the nodes of queue by following link parts while new node’s priority is greater than the priority of current traversed node.
- When a node with priority lesser than the new node is found, traversal terminates.
- New node is inserted between previous(prev) and current(ptr) nodes.
Program
#user defined class for nodes
class Node:
# constructor
def __init__(self, data=None, priority=None, link=None, ):
self.data=data
self.priority=priority
self.link=link
#print node's value and priority
def __str__(self):
return str(self.data+" ("+self.priority+")")
#user defined class for priority Queue
class ClassQueue:
#constructor for priority Queue Class
def __init__(self, front=None,nodecount=0):
self.front=front
self.nodecount=nodecount #keps track of number of nodes in priority queue
def enqueue(self, value=None, priority=None):#add new elements in Priority queue
node=Node(value,priority)
if self.front==None: #if queue is empty
node.link=None
self.front=node
else:
prev=None # if queue has existing nodes, locate correct position according to priority
ptr=self.front
while (priority>=ptr.priority):# compare priority
prev=ptr
ptr=ptr.link
if (ptr==None):#reaching end of queue
break
#add new node at postion according to sorted order of priorities
node.link=ptr
if prev==None:
self.front=node
else:
prev.link=node
self.nodecount=self.nodecount+1# increment node count in Priority queue
def dequeue(self):#delete elements
item=self.front.data
self.front=self.front.link
self.nodecount=self.nodecount-1 #decrement count of priority queue elements
return item
def printData(self):#traverse and display proority queue elements
ptr=self.front
while ptr:
print(ptr)
ptr=ptr.link
print()
#Create blank priority Queue
que=ClassQueue()
numele= input('How many elements to be added in the Priority queue??')
#add a few elements to initialise priority queue
for cnt in range(int(numele)):
ele= input('Enter a value')
pri= input('Enter priority')
que.enqueue(ele, pri)
cnt=cnt+1
#Print Queue adding or deleting elements
print("Priority Queue Initially")
que.printData()
#As user whether to insert or delete an element.
option='Y'
while (option=='Y' or option=='y'):
deem=int(input("Enter 1 for Insertion and 2 for Deletion"))
if (deem==1):
#calling class enqueue method to insert an element.
value=input("Enter the value to be Added")
Prior=input("Enter the Priority of this element")
que.enqueue(value, Prior)
que.printData()
elif (deem==2):
#calling class dequeue method to delete an element.
print("The popped value is",que.dequeue())
que.printData()
else:
print("Wrong option")
continue
option=str(input("do you want to do more operations(Y/N)??"))
#Print Queue again after operations
print("Priority Queue Finally")
que.printData()
Note: A Priority Queue is used to manage many tasks of Operating Systems. The common activities can be of job scheduling, prioritizing tasks and management of processes. Downloading of files through a browser can be understood as an example of Priority Queue where the smaller files have higher priority than the bulkier ones.
Be First to Comment