montón mínimo en python

Question

Me gustaría almacenar un conjunto de objetos en un montón mínimo mediante la definición de una función de comparación personalizada. Veo que hay un módulo heapq disponible como parte de la distribución de Python. ¿Hay alguna manera de usar un comparador personalizado con este módulo? Si no, ¿alguien más ha creado un montón de minutos personalizado?

Answer 1

Sí, hay una manera. Defina una clase de ajuste que implemente su comparador personalizado y use una lista de ellos en lugar de una lista de sus objetos reales. Eso es lo mejor que hay al usar el módulo heapq, ya que no proporciona ningún argumento key = o cmp = como lo hacen las funciones/métodos de clasificación.

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

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

1. Decora tus datos antes de utilizar el montón. Esto es el equivalente de la opción key= para clasificar. 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. Podrías copiarlo a tu directorio de trabajo y cambiar los bits relevantes. Desde un vistazo rápido, tendría que modificar siftdown() y siftup(), y posiblemente nlargest y nsmallest si los necesita.