Priority Queue Comparator in Python

1. Priority Queue in Python
2. Priority Queue Custom Comparator in Python
3. Priority Queue Using List in Python
4. Priority Queue Using heapdict Module in Python

This article will look into developing a custom priority queue with Python. In addition to that, we will also learn how we can utilize a custom comparator function with the priority queue.

Priority Queue in Python

A priority queue is a data structure that allows us to store items with a certain priority. The priority queue will then order the items so that the item with the highest priority is at the top of the queue.

A priority queue is often used in algorithms where we need to process the items in order of priority. Suppose we were processing a list of tasks; we would want to process the most important tasks first.

We can do it using a priority queue.

Priority Queue Custom Comparator in Python

The built-in module queue in Python provides a priority queue implementation. However, the module does not allow us to specify a custom comparator for the priority queue.

This can be a problem if we want to use a different ordering for the priority queue than the default ordering.

Fortunately, there is a way to create a custom comparator for a Python priority queue. In this article, we will see how to do this.

We will be exploring two examples of the priority queue.

1. Priority Queue Using the list in Python
2. Priority Queue Using the heapdict module of Python

Priority Queue Using List in Python

To begin, we will make a blank list. After that, we will add each person’s name to the list in order of importance.

We will start from 1 and move to ascend. Therefore, each name will be assigned a number, serving as the priority on the list.

The priority is an integer number that establishes the sequence in which the tasks will be carried out when they are eventually completed.

Let’s get it done by using the code. Firstly, we will create a list called names.

This list will be initially empty. See the code below.

names = []

Now, to add names to the list, we will use the append method that is easily accessible from the list functionalities. The append method requires two arguments to be sent in.

Add a number to the list to indicate the priority, number, name, or anything else. For our purposes, we would want the name Abid to appear at position1 on the list.

names.append((1, "Abid"))

There is no limit to the number of names or items that can be added, and the index numbers will indicate their order of priority.

Example code:

names.append((1, "Abid"))
names.append((4, "Jesica"))
names.sort(reverse=True)
names.append((3, "Anna"))
names.sort(reverse=True)
names.append((2, "Pat"))

The names list records will be printed out when we utilize the while loop here.

while names:
    print(names.pop())

This is the same code created before; copy it and execute it to see the results.

names = []
names.append((1, "Abid"))
names.append((4, "Jesica"))
names.sort(reverse=True)
names.append((3, "Anna"))
names.sort(reverse=True)
names.append((2, "Pat"))
names.sort(reverse=True)
while names:
    print(names.pop())

Output:

(1, 'Abid')
(2, 'Pat')
(3, 'Anna')
(4, 'Jesica')

This is the output of running the code. We can see clearly that each name is ordered according to the priority and index we provided.

Priority Queue Using heapdict Module in Python

The priority queue based on a heap is made accessible through the heapdict Python module. It is comparable to the normal heapq module but offers a greater variety of capabilities and adaptability.

A binary heap is the foundation of the heapdict data structure. A binary heap is a data structure that can be used to store data in a manner that facilitates the efficient retrieval and change of that data.

The binary heap is a full binary tree, which indicates that every node in the tree has two offspring, and the tree itself is always balanced.

HeapDict and HeapQueue are the two primary classes made available by the heapdict module. The heapdict class functions similarly to a dictionary and keeps its content in a heap.

A heap is used to hold the information managed by the queue-like class called HeapQueue. The HeapDict and the HeapQueue classes are built-in subclasses of the dict class.

They take on all of the dict’s methods and offer ways of interacting with heaps, which they inherit.

Please note that the heapdict module will not be automatically installed for us. We have to use the command that is shown below to configure heapdict.

pip install heapdict

After the completion of the installation of the heapdict library, we are now ready to make use of it in the process of implementing the priority queue.

1. The first step is to import the library of heapdict.
2. Make a variable that will be used to invoke the heapdict function, and continue using the variable for priority.
3. At this point, we will use the function we developed before to assign priorities to each task.
4. Utilize a while loop.
5. Display the result by printing the variable.

The whole code can be written in the following form.

import heapdict

tasks = heapdict.heapdict()
tasks["Breakfast"] = 3
tasks["Wake up"] = 1
tasks["Get ready for work"] = 4
tasks["Exercise"] = 2
while tasks:
    print(tasks.popitem())

Output:

('Wake up', 1)
('Exercise', 2)
('Breakfast', 3)
('Get ready for work', 4)

The output of the code demonstrates that the code is functioning correctly according to the priority order assigned to various tasks in the code. The output of our activities follows the same order and indicates the proper priority.

This article taught us how to build a priority queue by utilizing a list. In addition to that, we went through the steps necessary to create a custom priority queue in Python.

We are now aware of how to implement a custom comparator function with the priority queue.

We hope you find this article helpful in understanding how to create a custom priority queue in Python.