python中的最小堆

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

1> John Fouhy..：

---

两种选择(除了Devin Jeanpierre的建议):

在使用堆之前装饰您的数据.这相当于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]

该heapq模块以纯python实现.您可以将其复制到工作目录并更改相关位.从快速查看,您将不得不修改siftdown()和siftup(),如果需要,可能需要更新和最小化.

2> Devin Jeanpi..：

---

是的,有一种方法.定义一个实现自定义比较器的包装类,并使用它们的列表而不是实际对象的列表.这仍然是使用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

---

嗯.你应该定义__le__而不是__cmp__.这将保持Python 2/3的兼容性.毕竟,heapq操作和排序操作使用<=作为它们的比较函数.

---

请注意,这在python 3.0中不起作用,它消除了__cmp__.