Before you go ahead with understanding what a 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 its child nodes. Hence the minimum value is always on the top.
A priority queue can be of two types:
-
Max Priority Queue: Which arranges the data as per descending order of their priority.
-
Min Priority Queue: Which arranges the data as per ascending order of their priority.
In a priority queue, the following factors come into play:
-
In the priority queue, data, when inserted, is stored based on its priority.
-
When we remove data from a priority queue(min), the data at the top, which will be the data with the least priority, will get removed.
-
But, this way priority queue will not be following the basic principle 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:
-
Node: The Node class will be the element inserted in the priority queue. You can modify the Node class as per your requirements.
-
insert: To add a new data element(Node) in the priority queue.
-
If the priority queue is empty, we will insert the element into 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 a priority greater than the new node.
-
If the new node has the highest priority, then we will add the new node at the end.
-
delete: To remove the element with the least priority.
-
size: To check the size of the priority queue, in other words, count the number of elements in the queue and return it.
-
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.
NOTE: In the code above we haven't handled the duplicate node check, you should try to add that yourself.
Frequently Asked Questions
Here are some FAQs.
What are the applications of Priority Queue?
-
We can implement Prim's algorithm and Dijkstra's Shortest path algorithm using priority queues.
-
We can also use the Priority Queue for sorting Heap data structures.
-
In the Operating system, Priority queues are used for load balancing and interrupt handling.
-
Priority queues are also used in Huffman coding algorithm for data compression.
-
One real-time example is traffic lights based on the traffic congestion on road can be implemented using a Priority queue.
-
Hospital patient attendance based on the severity of the injury is an example of a priority queue, where each patient is assigned a priority based on their injury.
What are the operations of Priority Queue?
Following are the various operations needed in a Priority Queue:
push() operation to add an item to the priority queue.
pop() operation to remove an item.
top() operation to get the top priority item.
size() operation to return the number of items/elements in the priority queue.
empty() operation to check if priority queue is empty or not.
You may also like:
