heapq与自定义比较谓词

我正在尝试使用自定义sorting谓词来构build堆。 由于进入它的值是“用户自定义”types,所以我不能修改它们的内置比较谓词。

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

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

或者甚至更好,我可以包装heapq函数在我自己的容器中,所以我不需要继续传递谓词。

根据heapq文档 ,自定义堆顺序的方法是让堆中的每个元素都是一个元组,第一个元组是一个接受普通Python比较的元组。

heapq模块中的函数有点麻烦(因为它们不是面向对象的),而且总是要求我们的堆对象(一个堆积列表)作为第一个参数显式传递。 我们可以通过创build一个非常简单的包装类来杀死两只鸟,这将允许我们指定一个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] 

heapq文档build议堆元素可以是第一个元素是优先级的元组,并定义sorting顺序。

然而,与你的问题更为相关的是,这个文档包含了一个关于如何实现自己的heapq包装函数来处理sorting稳定性问题和同等重要的元素(以及其他问题)的示例代码的讨论 。

简而言之,他们的解决scheme是让heapq中的每个元素都是一个优先级,一个入口计数和要插入的元素的三元组。 入口计数确保具有相同优先级的元素按照它们被添加到堆中的顺序sorting。

两个答案的局限性在于,他们不允许关系被视为关系。 首先,通过比较项目来打破关系,通过比较input顺序来打破关系。 把联系关系联系起来会更快,如果联系很多的话,就会产生很大的影响。 基于上述和文件,目前尚不清楚这是否可以在heapq中实现。 看起来很奇怪,heapq不接受一个键,而在同一个模块中派生的函数也是这样做的。
PS:如果您按照第一条评论(“可能重复…”)中的链接,还有另一个定义le的build议,这似乎是一个解决scheme。