具有自定义比较谓词的heapq

Question

我正在尝试使用自定义排序谓词构建堆.由于进入它的值是'用户定义'类型,我无法修改它们的内置比较谓词.

有没有办法做这样的事情:

h = heapq.heapify([...], key=my_lt_pred)
h = heapq.heappush(h, key=my_lt_pred)

或者甚至更好,我可以将heapq函数包装在我自己的容器中,这样我就不需要继续传递谓词了.

Answer 1

根据heapq文档,自定义堆顺序的方法是使堆上的每个元素都成为元组,第一个元组元素是接受普通Python比较的元素.

heapq模块中的函数有点麻烦(因为它们不是面向对象的),并且总是要求我们的堆对象(堆化列表)作为第一个参数显式传递.我们可以通过创建一个非常简单的包装类来一举两得,它将允许我们指定一个key函数,并将堆作为一个对象呈现.

下面的类保留了一个内部列表,其中每个元素都是一个元组,其中第一个成员是一个键,使用key参数在元素插入时计算,在Heap实例化时传递:

# -*- coding: utf-8 -*-
import heapq

class MyHeap(object):
   def __init__(self, initial=None, key=lambda x:x):
       self.key = key
       if initial:
           self._data = [(key(item), item) for item in initial]
           heapq.heapify(self._data)
       else:
           self._data = []

   def push(self, item):
       heapq.heappush(self._data, (self.key(item), item))

   def pop(self):
       return heapq.heappop(self._data)[1]

Answer 2

定义一个类，在其中覆盖__lt__()函数。请参见下面的示例（适用于 Python 3.7）：

import heapq

class Node(object):
    def __init__(self, val: int):
        self.val = val

    def __repr__(self):
        return f'Node value: {self.val}'

    def __lt__(self, other):
        return self.val < other.val

heap = [Node(2), Node(0), Node(1), Node(4), Node(2)]
heapq.heapify(heap)
print(heap)  # output: [Node value: 0, Node value: 2, Node value: 1, Node value: 4, Node value: 2]

heapq.heappop(heap)
print(heap)  # output: [Node value: 1, Node value: 2, Node value: 2, Node value: 4]

Answer 3

所述heapq文档表明,堆元件可以是元组,其中所述第一元件是所述优先级,并限定的排序顺序.

然而,与您的问题更相关的是,文档中包含了一个示例代码的讨论,该示例代码说明了如何实现自己的heapq包装函数来处理排序稳定性问题和具有相同优先级的元素(以及其他问题).

简而言之,他们的解决方案是让heapq中的每个元素都是具有优先级的三元组,一个条目计数和要插入的元素.条目计数确保具有相同优先级的元素按照它们添加到heapq的顺序排序.

Answer 4

setattr(ListNode, "__lt__", lambda self, other: self.val <= other.val)

使用它来比较 heapq 中对象的值