Priority Queues in Python

What is a Priority Queue?
A queue has FIFO (first-in-first-out) ordering where items are taken out or accessed on a first-come-first-served basis.
A priority queue is an abstract data structure (a data structure defined by its behaviour) that is like a normal queue but where each item has a special “key” to quantify its “priority”.

Example : 
If Pizza shop decides to serve loyal customers first, it will order them by their loyalty (points or number of piza purchased by them in past).
In such a case, the queue for Piza buyer will no longer be first-come-first-served, but most-loyal-first-served.
The customers will be the “items” of this priority queue while the “priority” or “key” will be their loyalty.

Implementing Priority Queues in Python
Consider that we want to have a priority queue of customers based on their loyalty points. The higher the points, the more the priority.
Implementing Priority Queues in Python, there are a number of options. We will explore three of them.

Using a list
A very simple and straightforward way is to use the normal list but We have to sort it every time an item is added. Here’s an example:

# Priority Queues using List

customers = []

customers.append((2, "Saurabh")) #no sort needed here because 1 item.

customers.append((3, "Pheku"))

customers.sort(reverse=True)

#Need to sort to maintain order

customers.append((1, "Kumar"))

customers.sort(reverse=True)

#Need to sort to maintain order

customers.append((4, "Bhanu"))

customers.sort(reverse=True)

while customers:

print(customers.pop(0))

#Will print names in the order: Bhanu, Pheku, Saurabh, Kumar.

it takes O(n log n) time to maintain the order when an item is added to the list. Thus, it is only efficient when we have to make few insertions.
2. Using heapq
We can also use the heapq module in Python to implement our priority queue. This implementation has O(log n) time for insertion and extraction of the smallest element. Note that heapq only has a min heap implementation, but there are ways to use as a max heap.
Here’s an example:

# 2. Using heapq

import heapq

customers = []

heapq.heappush(customers, (2, "Harry"))

heapq.heappush(customers, (3, "Charles"))

heapq.heappush(customers, (1, "Riya"))

heapq.heappush(customers, (4, "Stacy"))

while customers:

print(heapq.heappop(customers))

#Will print names in the order: Riya, Harry, Charles, Stacy.

3. Using queue.PriorityQueue
This python inbuilt PriorityQueue uses the same heapq implementation, we discused in point no 2, internally and thus has the same time complexity.
However, it is different in two key ways. 

• Firstly, it is synchronized, so it supports concurrent processes
• Secondly, it is a class interface instead of the function based interface of heapq

Thus, PriorityQueue is the classic OOP style of implementing and using Priority Queues.
example:

# 3. Using queue.PriorityQueue

from queue import PriorityQueue

#we initialise the PQ class instead of using a function

# to operate upon a list.

customer1 = PriorityQueue()

customer1.put((2, "Khesav"))

customer1.put((3, "Madhav"))

customer1.put((1, "Hari"))

customer1.put((4, "Riya"))

while customer1:

print(customer1.get())

Thanks
Saurabh
Happy Coding !!!!