min montão no pitão

Question

Eu gostaria de armazenar um conjunto de objetos em um min pilha através da definição de uma função de comparação personalizada. Vejo que há um módulo heapq disponível como parte da distribuição python. Existe uma maneira de usar um comparador personalizado com este módulo? Se não, tem alguém construiu um costume min pilha?

Answer 1

Sim, há uma maneira. Definir uma classe de embrulho que implementa o seu comparador personalizado, e usar uma lista das pessoas em vez de uma lista de seus objetos reais. Isso é sobre o melhor que existe enquanto ainda estiver usando o módulo heapq, uma vez que fornece nenhuma tecla = ou CMP = argumentos como as funções de ordenação / métodos de fazer.

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

Duas opções (além da sugestão de Devin Jeanpierre):

1. Decore seus dados antes de usar o heap. Isso é o equivalente da opção key= a classificação. por exemplo. se você (por alguma razão) queria heapify uma lista de números de acordo com sua sine:

   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. O módulo heapq é implementado em python puro. Você poderia simplesmente copiá-lo para seu diretório de trabalho e alterar os bits relevantes. A partir de um olhar rápido, você teria que modificar siftdown () e siftup (), e, possivelmente, nlargest e nsmallest se você precisar deles.