priority queue – Custom comparator for building PriorityQueue in Python

priority queue – Custom comparator for building PriorityQueue in Python

Rather than inserting your elements directly into the queue, wrap each element in a tuple, where the first element in the tuple is the desired sorting key. Tuples are sorted by in order of their elements (i.e., first element is compared first), hence why the sorting key needs to come first.

import heapq

queue = []
my_list = [...]
for element in my_list:
    heapq.heappush(queue, (my_func(element), element))

If you have a wrapper class for the elements, then you can use operator overloading.

For example, lets say you have a CustomNumber class (equivalent to your elements) where the order is determined by the modulo 16 value (the private function __f()), the you can override the comparison operators like:

class CustomNumber:
    def __init__(self, value):
        self.value = value

    def __f(self, x):
        return x % 16

    def __lt__(self, obj):
        self < obj.
        return self.__f(self.value) < self.__f(obj.value)

    def __le__(self, obj):
        self <= obj.
        return self.__f(self.value) <= self.__f(obj.value)

    def __eq__(self, obj):
        self == obj.
        return self.__f(self.value) == self.__f(obj.value)

    def __ne__(self, obj):
        self != obj.
        return self.__f(self.value) != self.__f(obj.value)

    def __gt__(self, obj):
        self > obj.
        return self.__f(self.value) > self.__f(obj.value)

    def __ge__(self, obj):
        self >= obj.
        return self.__f(self.value) >= self.__f(obj.value)

Such that the following code:

a = CustomNumber(16)
b = CustomNumber(14)

print(a < b =, a < b)
print(a <= b =, a <= b)
print(a == b =, a == b)
print(a != b =, a != b)
print(a > b =, a > b)
print(a >= b =, a >= b)

prints:

a < b = True
a <= b = True
a == b = False
a != b = True
a > b = False
a >= b = False

priority queue – Custom comparator for building PriorityQueue in Python

The way you wrote your question, there is no way to achieve it. According to the documentation:

The lowest valued entries are retrieved first (the lowest valued entry is the one returned by sorted(list(entries))[0]). A typical pattern for entries is a tuple in the form: (priority_number, data).

In other words, the priority is defined by running sorted on the entries, and there is no way there to define the key parameter for that sorted run.

So, you cannot set a sort function when defining the PriorityQueue. You have to use one of the other solutions provided (or write your own PriorityQueue implementation, which should not be too hard).

Edit

After checking the code, I see that the documentation is not an exact description of how it works, but a simplification.

However, it also shows how easy it would be for you to make your own implementation.

Leave a Reply

Your email address will not be published. Required fields are marked *