Custom comparator for building PriorityQueue in Python

Question

Iam trying to build a priority queue using PriorityQueue in Python, but instead of element to be considered for priority comparison, I want it to use the return value from a function after passing the element to the function , similar to sorted(mtlist,key = myfun), is there a way to achieve this,

Abuttal

Do you want a "customer" comparator? Or a "custom" comparator? – Stray

Its custom, sorry for the typo – Abuttal

Answer 1

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))

Bidden

Thanks @mackorone, I ended up doing this :-) – Abuttal

This can cause bugs if my_func(element) is ever the same between two items... If that happens, the comparison falls back on element - which may not even be comparable, and will give you an annoying, very rare error. – Schmaltzy

but what if there are multiple keys? – Rejection

Thanks @Bidden . This code helped me a lot. I recommend Python users who don't know the sorting key of an element until said element is compared with another element in the priority queue to check out the functools.cmp_to_key wrapper and this StackOverflow response – Miscegenation

Answer 2

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

Sudorific

The only issue with this approach in relation to the question is that __f will be called multiple times per element when inserting/popping , if __f is an expensive calculation this is not optimal – Meitner

Yeah, it is not, you can "cache" this values instead. Check pydanny's implementation of cached properties: github.com/pydanny/cached-property – Sudorific

Answer 3

Here is an example of using custom sort in PriorityQueue in Python.

We use a priority-queue (heapq) find the next element to add. To make the
implementation simple we "monkey patch" the ListNode class to have a custom
 less-than function using setattr. Note that, simply using the tuple trick 
 and pushing (node.val, node) to the priority queue will not work because 
 the lists have values in common.

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    
    setattr(ListNode, "__lt__", lambda self, other: self.val <= other.val)
        
    pq = []
    for l in lists:
        if l:
            heapq.heappush(pq,  l)
    
    out = ListNode(None)
    head = out
    while pq:
        l = heapq.heappop(pq)
        head.next = l
        head = head.next
        if l and l.next:
            heapq.heappush( pq, l.next)
        
    return out.next

Flogging

Dude, I was doing an algo question and ran into this problem where if the value of two ListNodes is the same, it will give me that error. I didn't even know you can set attributes with setattr() before. This is so useful! Thank you for this fantastic answer! Take my upvote. – Chorale

welcome, i am happy that i am able to help you. – Flogging

Answer 4

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.

Hellgrammite