具有自定义比较谓词的 heapq
问题描述
我正在尝试使用自定义排序谓词构建堆.由于进入它的值是用户定义"类型，我无法修改它们的内置比较谓词.
I am trying to build a heap with a custom sort predicate. Since the values going into it are of 'user-defined' type, I cannot modify their built-in comparison predicate.
有没有办法做类似的事情:
Is there a way to do something like:
h = heapq.heapify([...], key=my_lt_pred)
h = heapq.heappush(h, key=my_lt_pred)
或者更好的是，我可以将 heapq 函数包装在自己的容器中，这样我就不需要继续传递谓词了.
Or even better, I could wrap the heapq functions in my own container so I don't need to keep passing the predicate.
解决方案
根据heapq 文档，自定义堆顺序的方法是让堆上的每个元素成为一个元组，第一个元组元素是一个接受普通 Python 比较的元素.
According to the heapq documentation, the way to customize the heap order is to have each element on the heap to be a tuple, with the first tuple element being one that accepts normal Python comparisons.
heapq 模块中的函数有点麻烦(因为它们不是面向对象的)，并且总是需要我们的堆对象(一个堆化列表)作为第一个参数显式传递.我们可以通过创建一个非常简单的包装类来用一块石头杀死两只鸟，它允许我们指定一个 key 函数，并将堆呈现为一个对象.
The functions in the heapq module are a bit cumbersome (since they are not object-oriented), and always require our heap object (a heapified list) to be explicitly passed as the first parameter. We can kill two birds with one stone by creating a very simple wrapper class that will allow us to specify a key function, and present the heap as an object.
下面的类保留一个内部列表，其中每个元素都是一个元组，其中第一个成员是一个键，在元素插入时使用 key 参数计算，在堆实例化时传递:
The class below keeps an internal list, where each element is a tuple, the first member of which is a key, calculated at element insertion time using the key parameter, passed at Heap instantiation:
# -*- coding: utf-8 -*-
import heapq
class MyHeap(object):
def __init__(self, initial=None, key=lambda x:x):
self.key = key
self.index = 0
if initial:
self._data = [(key(item), i, item) for i, item in enumerate(initial)]
self.index = len(self._data)
heapq.heapify(self._data)
else:
self._data = []
def push(self, item):
heapq.heappush(self._data, (self.key(item), self.index, item))
self.index += 1
def pop(self):
return heapq.heappop(self._data)[2]
(额外的 self.index 部分是为了避免在评估的键值是平局并且存储的值不能直接比较时发生冲突 - 否则 heapq 可能会因 TypeError 而失败)
(The extra self.index part is to avoid clashes when the evaluated key value is a draw and the stored value is not directly comparable - otherwise heapq could fail with TypeError)
相关文章