mucchio min in pitone

Question

Mi piacerebbe memorizzare una serie di oggetti in un mucchio min definendo una funzione di confronto personalizzato. Vedo che c'è un modulo di heapq disponibile come parte della distribuzione pitone. C'è un modo per utilizzare un comparatore personalizzato con questo modulo? In caso contrario, è qualcun altro costruito un costume min mucchio?

Answer 1

Sì, c'è un modo. Definire una classe involucro che implementa il vostro confronto personalizzato e utilizzare un elenco di coloro che, invece di una lista dei tuoi oggetti reali. Che è circa il meglio che c'è pur utilizzando il modulo heapq, in quanto fornisce nessuna chiave = o CMP = argomenti come le funzioni di ordinamento / metodi fanno.

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

Due opzioni (a parte il suggerimento di Devin Jeanpierre):

1. Decorate i vostri dati prima di utilizzare il mucchio. Questo è l'equivalente dell'opzione key= a cernita. per esempio. se (per qualche motivo) voleva heapify un elenco di numeri in base alla loro 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. Il modulo heapq è implementato in puro Python. Si potrebbe semplicemente copiare nella directory di lavoro e modificare i bit rilevanti. Da una rapida occhiata, si dovrebbe modificare siftdown () e siftup (), e possibilmente nlargest e nsmallest se ne avete bisogno.