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
        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()
Output Priority Queue

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

Leave a Reply

Your email address will not be published. Required fields are marked *