heapq与自定义比较谓词 [英] heapq with custom compare predicate
问题描述
我正在尝试使用自定义排序谓词构建堆。因为进入它的值是用户定义的类型,所以我无法修改其内置的比较谓词。
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.
有没有办法做到这一点: / p>
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模块中的函数有点麻烦(因为它们不是面向对象),并且总是需要我们的堆对象(堆叠列表)作为第一个参数被明确传递。通过创建一个非常简单的包装类,我们可以用一块石头杀死两只鸟,这样我们可以指定一个键
函数,并将堆呈现为一个对象。
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.
下面的类保存一个内部列表,其中每个元素是一个元组,其第一个成员是一个键,使用键在元素插入时计算
参数,在堆实例化中传递:
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
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与自定义比较谓词的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!