## Priority Queues in Python

A Priority Queue is an abstract data structure that is used to maintain a queue of data elements where each element is assigned a priority of precedence.

It is similar to a queue in implementation, but the only difference lies in the fact that Priority Queues have a certain priority attached to each of its elements. This priority is followed when the queue is dequeued.

Priority Queues are dynamic data structures. Also, any type of data can be stored in a Priority Queue.

Priority Queue nodes contain three fields; the data field, the priority field, and the link field which holds the link to the next element in the queue.

##### Factors that govern a Priority Queue
1. An element of higher priority will always be dequeued before an element with lower priority
2. Two elements having the same priority will be dequeued in First In First Out (FIFO) order

### Characteristics of Priority Queues

• Ordered - Elements are arranged in a certain order
• Mutable - Elements can be added/ deleted/ modified
• Dynamic - The data structure is dynamic ie. can be extended and shortened
• Any type of data can be stored
• Elements in the queue follow a certain priority of precedence

## Implementing a Priority Queue in Python

The implementation of a Priority Queue in Python is quite similar to the implementation of a normal Queue. The only difference lies in the fact that in this case, the priorities of the individual elements require to be considered.

A Priority Queue in Python can be implemented by following these steps.

1. Definition of the Node class in Priority Queues also has an extra field called priority, which stores the priority factor for each element of the Queue
``````class Node:
def __init__(self, val, priority):
self.value = val
self.priority = priority
self.next = None​``````
2. Defining the Priority Queue class
``class Pqueue:​``
3. Initializing the front and rear pointers for the Priority Queue
``````    def __init__(self):
self.Front = None
self.Rear = None​``````
4. Definition of the enqueue() method in a Priority Queue differs from a normal queue with respect to the priority factor that needs to be considered while adding elements to the queue
``def enqueue(self, val, priority=None):``
1. Checking whether or not a Priority Queue is empty and initializing it
``````        if self.empty() is True:
self.Front = Node(val, priority)
self.Rear = self.Front
return​``````
2. Creating the Node to be added
``inst = Node(val, priority)​``
3. Adding the Node to the Priority Queue based on its priority value, and in case of similar priority, according to the First in First out (FIFO) precedence
``````        if inst.priority < self.Front.priority:
inst.next = self.Front
self.Front = inst
elif inst.priority >= self.Rear.priority:
self.Rear.next = inst
self.Rear = self.Rear.next
elif inst.priority == self.Front.priority:
n = self.Front.next
f = self.Front
while n.priority == inst.priority:
n = n.next
f = f.next
f.next = inst
f.next.next = n
else:
f = self.Front.next
n = f.next
while n.priority <= inst.priority:
n = n.next
f = f.next
f.next = inst
f.next.next = n​``````
5. Defining the dequeue() method which is used to remove elements from the Priority Queue according to their priority values
``````    def dequeue(self):
if self.empty() is True:
print("Queue is empty")
return -1
elif self.Front == self.Rear:
temp = self.Front.value
self.Front = None
self.Rear = None
return temp
else:
temp = self.Front.value
self.Front = self.Front.next
return temp​``````
6. Defining the front() method which returns the front pointer of the Priority Queue
``````    def front(self):
if self.empty() is True:
print("Queue empty")
return -1
else:
return self.Front.value​``````
7. Defining the rear() method which returns the rear pointer element of the Priority Queue
``````    def rear(self):
if self.empty() is True:
print("Queue empty")
return -1
else:
return self.Rear.value​``````
8. Defining the empty() method which is used to check whether or not the Priority Queue is empty
``````    def empty(self):
if self.Rear is None:
return True
else:
return False​``````
9. The display() in the Priority Queue differs by the fact that the priorities require to be printed alongside the data values in a user-comprehendible format
``````    def display(self):
print("The Queue")
if self.empty() is True:
print("Queue empty")
elif self.Front == self.Rear:
print("val priority")
print(self.Front.value, "\t", self.Front.priority,  "<== FRONT <== REAR")
else:
i = self.Front.next
print("val priority")
print(self.Front.value, "\t", self.Front.priority, "<== FRONT")
while i is not self.Rear:
print(i.value, "\t", i.priority)
i = i.next
print(self.Rear.value, "\t", self.Rear.priority, "<== REAR")
print("Queue Over")``````
10. The Python 3 code implementing a Priority Queue, using the object-oriented characteristic, implementing the methods manipulating it, and creating an instance of it is as follows
``````class Node:
def __init__(self, val, priority):
self.value = val
self.priority = priority
self.next = None

class Pqueue:
def __init__(self):
self.Front = None
self.Rear = None

def enqueue(self, val, priority=None):
if self.empty() is True:
self.Front = Node(val, priority)
self.Rear = self.Front
return
inst = Node(val, priority)
if inst.priority < self.Front.priority:
inst.next = self.Front
self.Front = inst
elif inst.priority >= self.Rear.priority:
self.Rear.next = inst
self.Rear = self.Rear.next
elif inst.priority == self.Front.priority:
n = self.Front.next
f = self.Front
while n.priority == inst.priority:
n = n.next
f = f.next
f.next = inst
f.next.next = n
else:
f = self.Front.next
n = f.next
while n.priority <= inst.priority:
n = n.next
f = f.next
f.next = inst
f.next.next = n

def dequeue(self):
if self.empty() is True:
print("Queue is empty")
return -1
elif self.Front == self.Rear:
temp = self.Front.value
self.Front = None
self.Rear = None
return temp
else:
temp = self.Front.value
self.Front = self.Front.next
return temp

def front(self):
if self.empty() is True:
print("Queue empty")
return -1
else:
return self.Front.value

def rear(self):
if self.empty() is True:
print("Queue empty")
return -1
else:
return self.Rear.value

def empty(self):
if self.Rear is None:
return True
else:
return False

def display(self):
print("The Queue")
if self.empty() is True:
print("Queue empty")
elif self.Front == self.Rear:
print("val priority")
print(self.Front.value, "\t", self.Front.priority,  "<== FRONT <== REAR")
else:
i = self.Front.next
print("val priority")
print(self.Front.value, "\t", self.Front.priority, "<== FRONT")
while i is not self.Rear:
print(i.value, "\t", i.priority)
i = i.next
print(self.Rear.value, "\t", self.Rear.priority, "<== REAR")
print("Queue Over")

a = Pqueue()
a.enqueue(1, 2)
a.enqueue(2, 1)
a.enqueue(5, 1)
a.enqueue(9, 0)
a.enqueue(10, 3)
a.display()
print(a.dequeue())
a.display()
print(a.front())
a.dequeue()
print(a.rear())
a.display()
a.dequeue()
a.dequeue()
a.display()
a.dequeue()
a.display()``````

the output being

``````The Queue
val priority
9 	 0 <== FRONT
2 	 1
5 	 1
1 	 2
10 	 3 <== REAR
Queue Over
9
The Queue
val priority
2 	 1 <== FRONT
5 	 1
1 	 2
10 	 3 <== REAR
Queue Over
2
10
The Queue
val priority
5 	 1 <== FRONT
1 	 2
10 	 3 <== REAR
Queue Over
The Queue
val priority
10 	 3 <== FRONT <== REAR
Queue Over
The Queue
Queue empty
Queue Over``````

• The priority factor enables weighted advantage of certain nodes over others
• Easy to correct
• Easy to implement
• Dynamic memory allocation enabled