Priority Queue in Python
What is Queue?
Queue is a fundamental data structure following the First-In-First-Out(FIFO) rule. It is just like arrays or lists as organizing or representing the data in an ordered list. The main thing in the queue is it follows FIFO, where the items are removed as they are inserted. The one which is inserted first will be deleted or removed. In the queue, insertion will be held on one end, and deletion or removal of the element will be done on the other end. The insertion and deletion of elements or items will not be done randomly.
Consider a Ticket counter where people line up to buy tickets. The first person will purchase the ticket as he stands first in the line, then the next person. The people standing in line follow a rule called FIFO(First-In-First-Out). The queues can be implemented or supported through its libraries. In built-in classes, We have to create an object for the queue and call the method to add and remove new items.
What is a Priority Queue?
Priority Queue belongs to the Queue data structure where the elements are assigned or associated with a priority value. The priority queue does not store the elements in insertion order; instead, it stores them based on priority.
A variety of real-world scenarios can benefit from priority queues. Airlines, for instance, need to have priority when boarding an airplane. Customers traveling in business class form the highest priority queue and board first. Then, any standby or cheap fare passengers are given priority, followed by one or more normal fare lineups. Business travellers board first if they arrive after ordinary fare passengers have already begun to board. In a hospital, priority queuing is utilized as well for intake and to handle maintenance requests.
Operations in the Priority Queue
Here are some basic operations in the priority queue, such as:
- Insertion: The insertion or addition of an element with its priority to the priority queue is done using the put() method. Two parameters are required by the put() method: the item to be added and its priority. Usually, the item and priority are supplied as a tuple or other similar object. To ensure that items with higher priorities are positioned closer to the front of the queue, the element is added to the queue depending on its priority value.
- Retrieve: The element with the highest priority is retrieved and deleted using the get() function. The order of retrieval is decided by the order in which the items have been placed if more than one item has the same highest priority. The retrieved element is returned by the get() function so that you may continue processing it by ensuring that higher-priority items are handled first.
- Empty: The priority queue's empty is checked using the empty() method. If the queue is empty Boolean value will be returned as accurate, and it concludes that there are no elements in the queue. If the queue has one or more elements, on the other hand, it returns False. Before continuing with additional processing, this action enables you to check the queue for any pending tasks.
- Obtaining size: The size () procedure returns the priority queue's size, or the number of data entries, as of the current time. The method's return value is an integer representing the number of entries in the queue when it was called. This action helps determine the workload that is still outstanding in the queue or for monitoring the queue's capacity.
Example for Priority Queue
import queue
# Create an instance of PriorityQueue
my_priority_queue = queue.PriorityQueue()
# Inserting elements with their priorities
my_priority_queue.put((2, 'Task 2'))
my_priority_queue.put((1, 'Task 1'))
my_priority_queue.put((3, 'Task 3'))
# Retrieving and processing elements based on priority
while not my_priority_queue.empty():
priority, task = my_priority_queue.get()
print(f"Processing: {task}")
Output:
![Priority Queue in Python](https://static.tutorialandexample.com/python/priority-queue-in-python1.png)
Explanation:
The given Python code illustrates how to use a priority queue. It constructs an object called "My_PriorityQueue" with the property "PriorityQueue" and inserts components with the corresponding priorities into it. The while loop allocates elements to the priority and task variables after retrieving them from the queue according to their priority.
The code then prints the job being processed. Due to this loop, the components are processed in the order of their priority values, which keeps going until the priority queue is empty.