python中的最小堆

问题描述

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

I'd like to store a set of objects in a min heap by defining a custom comparison function. I see there is a heapq module available as part of the python distribution. Is there a way to use a custom comparator with this module? If not, has someone else built a custom min heap?

推荐答案

是的，有一种方法.定义一个实现您的自定义比较器的包装类，并使用这些包装的列表而不是您的实际对象的列表.在仍然使用heapq模块的同时，这是最好的，因为它不像排序函数/方法那样提供key =或cmp =参数.

Yes, there is a way. Define a wrapping class that implements your custom comparator, and use a list of those instead of a list of your actual objects. That's about the best there is while still using the heapq module, since it provides no key= or cmp= arguments like the sorting functions/methods do.

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

这篇关于python中的最小堆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！