# Priority Queue Python

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
#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
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
if (ptr==None):#reaching end of queue
break
#add new node at postion according to sorted order of priorities
if prev==None:
self.front=node
else:
self.nodecount=self.nodecount+1# increment node count in Priority queue
def dequeue(self):#delete elements
item=self.front.data
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)
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.