минимальная куча в python

Question

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

Answer 1

Да, способ есть.Определите класс упаковки, который реализует ваш пользовательский компаратор, и используйте их список вместо списка ваших реальных объектов.Это лучшее, что есть при использовании модуля 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

Answer 2

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

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 модуль реализован на чистом python.Вы могли бы просто скопировать его в свой рабочий каталог и изменить соответствующие биты.При беглом просмотре вам придется изменить siftdown() и siftup(), и, возможно, nlargest и nsmallest, если они вам нужны.