python - python中的最小堆

Question

我想通过定义自定义比较函数将一组对象存储在最小堆中。我看到有一个 heapq 模块可用作 python 发行版的一部分。有没有办法在这个模块中使用自定义比较器？如果没有，其他人是否构建了自定义最小堆？

Answer 1

两个选项（除了 Devin Jeanpierre 的建议）：

1. 在使用堆之前修饰你的数据。这相当于key=排序选项。例如，如果您（出于某种原因）想根据其正弦值堆积一个数字列表：

   data = [ # list of numbers ]
   heap = [(math.sin(x), x) for x in data]
   heapq.heapify(heap)
   # get the min element
   item = heappop(heap)[1]
   

2. 该heapq模块是用纯python实现的。您可以将其复制到您的工作目录并更改相关位。快速浏览一下，您必须修改 siftdown() 和 siftup()，如果需要，可能还需要修改 nlargest 和 nsmallest。

Answer 2

是的，有办法。定义一个实现自定义比较器的包装类，并使用它们的列表而不是实际对象的列表。这是仍然使用 heapq 模块时最好的情况，因为它没有提供 key= 或 cmp= 参数，就像排序函数/方法所做的那样。

def gen_wrapper(cmp):
    class Wrapper(object):
        def __init__(self, value): self.value = value
        def __cmp__(self, obj): return cmp(self.value, obj.value)
    return Wrapper