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。
