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
- 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))
- 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.
- 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.
#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.