мин куча в питоне

Question

Я бы хотел сохранить набор объектов в куче мин, определив пользовательскую функцию сравнения. Я вижу, что есть модуль heapq, доступный как часть дистрибутива Python. Есть ли способ использовать пользовательский компаратор с этим модулем? Если нет, то кто-нибудь еще создал собственную кучу мин?

Answer 1

Два варианта (кроме предложения Девина Жанпьера):

1. Украсьте свои данные перед использованием кучи. Это эквивалентно опции key= для сортировки. например если вы (по какой-то причине) хотели составить список чисел согласно их синусу:

   data = [ # list of numbers ]
   heap = [(math.sin(x), x) for x in data]
   heapq.heapify(heap)
   # get the min element
   item = heappop(heap)[1]
   

2. Модуль heapq реализован на чистом питоне. Вы можете просто скопировать его в свой рабочий каталог и изменить соответствующие биты. При быстром взгляде вам придется изменить siftdown () и siftup (), и, возможно, самый длинный и самый маленький, если они вам нужны.

Answer 2

Да, есть способ. Определите класс обертки, который реализует ваш собственный компаратор, и используйте их список вместо списка ваших реальных объектов. Это лучшее из того, что есть при использовании модуля heapq, поскольку он не предоставляет аргументов key = или cmp =, как это делают функции / методы сортировки.

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