Program for Priority Queue in Python
FREE
Overview
A Priority Queue is one of the most important queue functions. A priority queue is programmed to operate the queue in the specified order. A basic queue operates in the "FIFO (First In, First Out)" order, which means that the element entered into the queue first will likewise be withdrawn first.
However, we may not always want our queue to work in this manner; instead, we may want it to obey a different set of rules. This is where priority queues come into play, allowing us to retrieve queue elements in the order of our choice.
What are Priority Queues?
- A queue uses basic FIFO (first-in, first-out) ordering, which means that items are removed or accessed on a first-come, first-served basis. In such cases, there are no exceptions the oldest item must always be eliminated first. A queue at a railway ticket counter is an example of a strict queue. At times, this limitation is too inflexible. However, Prioritization can be added to the queue structure. This allows an entry to jump to the start of the queue even though it was not the first to arrive.
- A Priority Queue is an abstract data structure (a data structure defined by its behavior) that follows basic queueing principles while also maintaining various sub-queues for different priority levels.
- It prioritizes the set of entries before sorting them. Even if lower-priority items arrive earlier, the highest-priority entries are always treated first. In reality, the internal implementation of a priority queue rarely creates several lists. Instead, the priority determines where the new item should be placed. This ensures that the head of the queue is always handled first, but additional items are not instantly added to the back of the queue. In fact, it is possible that a very high-priority item may be placed at the front of the queue.
- Priority queues are beneficial in many real-world scenarios. For example, when boarding a flight, airlines enforce priority queuing. Passengers of business class from the highest priority queue are boarded first. Following that, any standby or low-priced passengers are prioritized, followed by one or more regular fare queues. If a business class passenger arrives after standard fare passengers have already boarded, they are moved to the front of the queue. Priority queuing is also applied in hospitals for triage or service maintenance requests.
- Priority queues are used in computing situations by multi-threaded operating systems. Higher priority tasks are prioritized first over background tasks. For example, mouse clicks take precedence over web page rendering. Routing updates and control traffic are prioritized in network routers over user traffic.
Difference between Queues and Priority Queues?
Queues: The queue is a critical data structure, but its utility varies depending on how it is implemented. A queue data structure is very simple to understand. Like the queues in real life, the first person to enter the queue is the first person to be taken out, i.e. FIFO- first in, first out. For example, suppose we entered these integers in the following order: 6 → 3 → 8 → 2 to the queue. Then, when you pop the values from it: the order of their pop will be: 6 → 3 → 8 → 2, i.e. the same order as when they were inserted. As 6 was entered first, it will be removed before the rest.
Priority Queues: Priority Queue is also a type of queue that has something to do with priority. When removing values from PQ, the highest priority entry is deleted first (not following the FIFO order as in normal Queues).
Consider the following insertion order: A(P=4) → B(P=3)→ C(P=5) → D(p=9) So, when removing from PQ, the removal sequence will be: D(P=9) → C(P=5) → A(P= 4) → B(P=3)
Note:
- The oldest element in Queue is dequeued first. In Priority Queue, an element is dequeued based on its highest priority.
- When elements are removed from a priority queue, the result is either sorted in increasing or decreasing order. When elements are popped from a basic queue, the outcome is a FIFO order of data.
queue.PriorityQueue class in Python
In Python, using Python lists you can create your own priority queues. It is preferable to use the built-in PriorityQueue class. This class provides very efficient support for all basic methods such as put and get. Python automatically inserts and removes entries based on their priority while also maintaining the internal structure of the queues.
A priority queue Python always removes and returns the item with the highest priority in the queue. Priority queue Python eliminates the item that arrived first if two items have the same priority. Python compares the priority and then the data item in a tuple with both priority and data fields.
Priority Queue Python is an extension of the Python heapq module, which is based on a binary heap design. It is quite simple to obtain and remove the item with the highest priority from a binary heap. Even when re-balancing actions are taken into account, insertions and deletions have a time complexity of O(log n).
As a result, even with large data sets, the PriorityQueue class remains quite efficient. In a max heap implementation, the top of the heap is always immediately accessible for the item with the highest priority at the front of the queue. Even though adding an item to the queue requires additional work, but it can still be completed in logarithmic time.
Implementation of Priority Queue in Python
Importing PriorityQueue
The queue module includes the PriorityQueue class. We can import the PriorityQueue class by executing the following command.
The above command enables immediate access to the constructor and all the class methods to be directly accessed without prepending the name of the module. For example, the following command can be used to construct a priority queue.
If you require additional functions from the queue library, you can import the full package.
In this case, the module name must come before the PriorityQueue constructor. The following line creates the same priority queue as the preceding example did.
How to make use of the PriorityQueue class?
The PriorityQueue class has many of the same methods as its parent Queue class.
Using the class constructor, a user can create a PriorityQueue object. At the same time, a user can provide a parameter to set the maximum size for the queue. The below command constructs a priority queue python with a capacity of 200 objects.
The interface of the PriorityQueue is fairly simple to use. The functions described in the following list are the most important.
| Function | Description |
|---|---|
| empty | If the queue is empty and has no items, this function returns True. If not, it returns False. This function is frequently used to determine if more get operations are required to service the queue. |
| full | If the queue has reached its maximum capacity and there is no more space for new entries then this function returns True. A queue can normally achieve full capacity only if a size limit is set. Otherwise, the queue's size is restricted only by available memory. |
| get | The get function is used to remove and return the item with the highest priority from the queue. Additional parameters define the length of the waiting period as well as how long Python has to wait. The block parameter has a default value of True, whereas the timeout parameter has a default value of None. By default, a get request blocks waiting forever for the next item to arrive. |
| put | The put function adds a priority-specified item to the priority queue. Developers can add a tuple in the form (priority number, data) or a single value to the function as a priority. A Python tuple is an immutable and ordered list. This method accepts block and timeout parameters, just like the get method. True and None are default values of this function. When there are no more open slots in the queue, the put method blocks until it runs out of time. |
| maxsize | This function returns the maximum size of the queue. It returns 0 if there is no maximum size. |
| qsize | This function returns the total number of items present in the queue at the moment. |
Note: Some of the PriorityQueue commands, such as full, empty, and qsize, may be prone to race conditions when multiple processes are in use.
We can delete a queue using the del command.
An Example of a Priority Queue in Python
The below example shows how to use the PriorityQueue class to create a Python priority queue for airline passengers. It demonstrates the creation of a queue, the addition and deletion of new entries, and how to delete all remaining items from the queue.
- The first step is to import the PriorityQueue package from the queue module.
- Create a Python PriorityQueue and give the variable p to the object.
- Using the put method, create three passengers. Passenger Naman is in business class, which has a priority 2, and passenger Deepika is in first class, which has a priority 1. The passenger Sikha is in the "standby" class 4. Each item is stored as a tuple that includes the priority and the passenger's name. The tuple is surrounded in parentheses and is the only parameter supplied to the put() method.
- Remove passenger Deepika, who is the highest priority passenger, from the queue. Even though Deepika arrived after Naman, she has the highest priority because she has a class value of 1.
- It is often useful to check whether the queue is empty or full. The empty method will return False, as there are still two items remaining. In practice, the queue has an infinite capacity, thus full is also False.
- Passenger Aditya has been added to the queue with "standard" class priority 3.
- Take the next passenger out of the queue. This is Naman, the passenger.
- Use a while loop to delete any leftover items from the priority queue. At the loop entry, confirm whether the loop contains any items or not. If the empty method returns true then the loop is empty but if it returns false, there are still entries to be found. In this case, the get method retrieves the item with the highest priority from the queue. Aditya is given a higher priority and gets removed from the queue before Sikha.
Note: If you use get with default parameters on an empty queue, it will be blocked until an item becomes available. To avoid the deadlock condition, either set the block option to False or first check whether the queue still has any entries.
- The queue will be empty at this point.
The entire set of commands can be combined to form a program.
Output of the above code:
Time Complexity
The Time complexity to implement Priority Queues by using heap data structure is:
| Operation | Worst-case Time Complexity |
|---|---|
| Insertion | O(log(n)) |
| Deletion | O(log(n)) |
Examples of Priority Queue in Python
Consider that we want to create a priority queue of passengers based on their loyalty points. The greater the number of points, the higher the priority. There are several approaches of implementing Priority Queues in Python. We'll look at three of them here.
1) Using a list
Using the usual list but sorting it every time an item is added is a very simple and straightforward method.
Here's an example:
Output of the above code:
However, when an item is added to the list it takes O(n log n) time to maintain the order. As a result, it is only efficient when only a few insertions are required.
2) Using heapq
To implement a priority queue, we can also use the heapq module in Python. Insertion and extraction of the smallest element take O(log n) time in this implementation. It should be noted that heapq only has a min heap implementation, however, there are ways to use it as a max heap as well.
Here’s an example:
Output of the above code:
3) Using queue.PriorityQueue
Internally, the PriorityQueue uses the same heapq implementation and hence has the same temporal complexity. However, it differs in two important aspects. Firstly, it is synchronized, which allows it to accommodate concurrent processes. Secondly, it is a class interface rather than heapq function-based interface. Thus, PriorityQueue is the traditional OOP approach of implementing and using Priority Queues.
Let's create a priority queue for our movie buffs:
Output of the above code:
FAQs
Q1.) Why shouldn't you keep a List?
Technically, a priority queue can be created using the Python list data structure. To do so, make a list and then sort it in ascending order.
A: However, this is a relatively inefficient method of maintaining a priority queue. When you change things on the list, you must re-order the list, which takes time.
If you simply need to hold a few values, a standard list can be used as a priority queue. On the other hand, lists are not a good option for creating a larger queue.
Q2.) What is the difference between a Priority Queue and a min heap?
A: A Priority Queue is a heap implementation. Therefore, this implementation can be either a max heap or a min heap. If Priority Queue is implemented as a max-heap, it will be a max-priority queue. Similarly, if the implementation is a min-heap, then Priority Queue will be a min-priority queue.
The smallest node in a min-heap is the root of the binary tree. Both priority queue and min heap are the same things. The only difference is that in a priority queue, the order of the elements is determined by their priority number.
Conclusion
- Python is one of the most well-known and widely used programming languages. Like other programming languages, it has a number of functions and libraries for implementing fundamental data structures.
- Like stack, queues are a useful linear data structure that performs FIFO (First In, First Out) processing on a list of objects. Traditional queues use a strict FIFO mechanism, however, Python priority queues can prioritize list entries. This enables high-priority things to be handled ahead of lower-priority ones that arrived earlier.
- The queue module in Python contains a priority queue implementation. It uses a heap data structure to manage priority queues. The value of the parent node in a max heap is greater than the value stored in any of its children.
- With a logarithmic time complexity, heaps make it straightforward to obtain the highest-priority item, and even insertions are quite efficient. Python priority queues feature a straightforward and basic interface. Put and get methods can be used to insert and retrieve items.
- The heapq module and the queue.PriorityQueue are the two most commonly used to generate a priority queue in Python. While a list can technically be used as a priority queue, it does not scale effectively.