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

Question

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

Answer 1

与其将元素直接插入队列，不如将每个元素包装在一个元组中，其中元组中的第一个元素是所需的排序键。元组按其元素的顺序排序（即，首先比较第一个元素），因此排序键需要排在第一位。import heapqqueue = []my_list = [...]for element in my_list:    heapq.heappush(queue, (my_func(element), element))

Answer 2

如果您有元素的包装类，那么您可以使用运算符重载。例如，假设您有一个CustomNumber类（相当于您的元素），其中顺序由模 16 值（私有函数__f()）确定，您可以覆盖比较运算符，例如：class CustomNumber:&nbsp; &nbsp; def __init__(self, value):&nbsp; &nbsp; &nbsp; &nbsp; self.value = value&nbsp; &nbsp; def __f(self, x):&nbsp; &nbsp; &nbsp; &nbsp; return x % 16&nbsp; &nbsp; def __lt__(self, obj):&nbsp; &nbsp; &nbsp; &nbsp; """self < obj."""&nbsp; &nbsp; &nbsp; &nbsp; return self.__f(self.value) < self.__f(obj.value)&nbsp; &nbsp; def __le__(self, obj):&nbsp; &nbsp; &nbsp; &nbsp; """self <= obj."""&nbsp; &nbsp; &nbsp; &nbsp; return self.__f(self.value) <= self.__f(obj.value)&nbsp; &nbsp; def __eq__(self, obj):&nbsp; &nbsp; &nbsp; &nbsp; """self == obj."""&nbsp; &nbsp; &nbsp; &nbsp; return self.__f(self.value) == self.__f(obj.value)&nbsp; &nbsp; def __ne__(self, obj):&nbsp; &nbsp; &nbsp; &nbsp; """self != obj."""&nbsp; &nbsp; &nbsp; &nbsp; return self.__f(self.value) != self.__f(obj.value)&nbsp; &nbsp; def __gt__(self, obj):&nbsp; &nbsp; &nbsp; &nbsp; """self > obj."""&nbsp; &nbsp; &nbsp; &nbsp; return self.__f(self.value) > self.__f(obj.value)&nbsp; &nbsp; def __ge__(self, obj):&nbsp; &nbsp; &nbsp; &nbsp; """self >= obj."""&nbsp; &nbsp; &nbsp; &nbsp; 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 = Truea <= b = Truea == b = Falsea != b = Truea > b = Falsea >= 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 theimplementation simple we "monkey patch" the ListNode class to have a custom&nbsp;less-than function using setattr. Note that, simply using the tuple trick&nbsp;&nbsp;and pushing (node.val, node) to the priority queue will not work because&nbsp;&nbsp;the lists have values in common.class Solution:&nbsp; &nbsp; def mergeKLists(self, lists: List[ListNode]) -> ListNode:&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; setattr(ListNode, "__lt__", lambda self, other: self.val <= other.val)&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; pq = []&nbsp; &nbsp; for l in lists:&nbsp; &nbsp; &nbsp; &nbsp; if l:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; heapq.heappush(pq,&nbsp; l)&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; out = ListNode(None)&nbsp; &nbsp; head = out&nbsp; &nbsp; while pq:&nbsp; &nbsp; &nbsp; &nbsp; l = heapq.heappop(pq)&nbsp; &nbsp; &nbsp; &nbsp; head.next = l&nbsp; &nbsp; &nbsp; &nbsp; head = head.next&nbsp; &nbsp; &nbsp; &nbsp; if l and l.next:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; heapq.heappush( pq, l.next)&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; return out.next