min heap in python

Question

Vorrei memorizzare un set di oggetti in un heap minimo definendo una funzione di confronto personalizzata. Vedo che c'è un modulo heapq disponibile come parte della distribuzione python. C'è un modo per usare un comparatore personalizzato con questo modulo? In caso contrario, qualcun altro ha creato un heap minimo personalizzato?

Answer 1

Sì, c'è un modo. Definisci una classe di wrapping che implementa il tuo comparatore personalizzato e utilizza un elenco di quelli al posto di un elenco dei tuoi oggetti reali. Questo è quanto di meglio ci sia mentre si usa ancora il modulo heapq, poiché non fornisce argomenti key = o cmp = come le funzioni/metodi di ordinamento.

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. Decora i tuoi dati prima di utilizzare l'heap. Questo è l'equivalente dell'opzione key= all'ordinamento. 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. Potresti semplicemente copiarlo nella tua directory di lavoro e cambiare i bit rilevanti. Da un rapido sguardo, dovresti modificare siftdown() e siftup(), e probabilmente nlargest e nsmallest se ne hai bisogno.