Implementing Priority Queue in Python

Before you go ahead with understanding what Priority Queue is, we recommend you to first understand the concept and implementation of a Queue and Circular Queue.

If you are a Youtuber, and you want to keep a track of the video published by you which has the least number of views, then a priority queue or a min heap can help you.

A Heap is a binary tree in which the value of every parent node is less than it's child nodes. Hence the minimum value is always on the top.

A priority queue can be of two types:

1. Max Priority Queue: Which arranges the data as per descending order of their priority.
2. Min Priority Queue: Which arranges the data as per ascending order of their priority.

In a priority queue, following factors come into play:

1. In priority queue, data when inserted, is stored based on its priority.
2. When we remove a data from a priority queue(min), the data at the top, which will be the data with least priority, will get removed.
3. But, this way priority queue will not be following the basic priniciple of a queue, First in First Out(FIFO). Yes, it won't! Because a priority queue is an advanced queue used when we have to arrange and manipulate data as per the given priority.

---

Implementing Priority Queue

So now we will design our very own minimum priority queue using python list and object oriented concept.

Below are the algorithm steps:

1. Node: The Node class will be the element inserted in the priority queue. You can modify the Node class as per your requirements.
2. insert: To add a new data element(Node) in the priority queue.
   • If the priority queue is empty, we will insert the element to it.
   • If the priority queue is not empty, we will traverse the queue, comparing the priorities of the existing nodes with the new node, and we will add the new node before the node with priority greater than the new node.
   • If the new node has the highest priority, then we will add the new node at the end.
3. delete: To remove the element with least priority.
4. size: To check the size of the priority queue, in other words count the number of elements in the queue and return it.
5. show: To print all the priority queue elements.

We will be using Python List for implementing queue data structure.

NOTE: We can also use the heapq library to implement Priority Queue(heap) in python.

Try changing the code as you like. Click the button, to Run the code again.

NOTE: In the code above we haven't handled the duplicate node check, you should try to add that yourself.