用于在 Python 中构建 PriorityQueue 的自定义比较器

Question

我正在尝试在 Python 中使用 PriorityQueue 构建优先级队列，但不是要考虑进行优先级比较的元素，而是希望它在将元素传递给函数后使用函数的返回值，类似于 sorted(mtlist,key = myfun），有没有办法做到这一点，

Answer 1

与其将元素直接插入队列，不如将每个元素包装在一个元组中，其中元组中的第一个元素是所需的排序键。元组按其元素的顺序排序（即，首先比较第一个元素），因此排序键需要排在第一位。

import heapq

queue = []

my_list = [...]

for element in my_list:

    heapq.heappush(queue, (my_func(element), element))

Answer 2

如果您有元素的包装类，那么您可以使用运算符重载。

例如，假设您有一个CustomNumber类（相当于您的元素），其中顺序由模 16 值（私有函数__f()）确定，您可以覆盖比较运算符，例如：

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)

这样下面的代码：

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)

印刷：

a < b = True

a <= b = True

a == b = False

a != b = True

a > b = False

a >= b = False

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