montón min en pitón

Question

Me gustaría para almacenar un conjunto de objetos en un montón min mediante la definición de una función de comparación personalizado. Veo que hay un módulo heapq disponible como parte de la distribución de pitón. ¿Hay una manera de utilizar un comparador de encargo con este módulo? Si no es así, se ha construido otra persona una costumbre min montón?

Answer 1

Sí, hay una manera. Definir una clase envoltorio que implementa el comparador de costumbre, y utilizar una lista de las personas en lugar de una lista de los objetos reales. Eso es lo mejor que hay sin dejar de utilizar el módulo heapq, ya que proporciona ninguna tecla = o = cmp argumentos como las funciones de clasificación / métodos de hacer.

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

Hay dos opciones (aparte de la sugerencia de Devin Jeanpierre):

1. Decora tus datos antes de utilizar el montón. Esto es el equivalente a la opción key= a la clasificación. p.ej. si (por alguna razón) quería heapify una lista de números de acuerdo a su seno:

   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. El módulo heapq está implementado en Python puro. Se podía copiarlo en el directorio de trabajo y cambiar los bits correspondientes. De un vistazo rápido, que tendría que modificar siftdown () y siftup (), y posiblemente nlargest y nsmallest si los necesita.