min Haufen in Python

Question

Ich möchte eine Reihe von Objekten in einem min-Heap speichern, indem Sie eine benutzerdefinierte Vergleichsfunktion definieren. Ich sehe, gibt es einen heapq Modul als Teil der Python-Distribution. Gibt es eine Möglichkeit, eine benutzerdefinierte Komparator mit diesem Modul zu benutzen? Wenn nicht, hat eine eingebaute jemand anderes eine benutzerdefinierte min Haufen?

Answer 1

Ja, es gibt einen Weg. Definieren Sie eine Verpackung Klasse, die Ihre benutzerdefinierten Komparator implementiert, und verwenden Sie eine Liste von denen statt einer Liste Ihrer eigentlichen Objekte. Das ist ungefähr das Beste, was es ist, während immer noch die heapq Modul verwenden, da es keinen Schlüssel = oder cmp = Argumente wie die Sortierfunktionen bietet / Methoden tun.

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

Zwei Optionen (abgesehen von Devin Jeanpierre Vorschlag):

1. Dekorieren Sie Ihre Daten vor dem Heap verwenden. Dies entspricht der key= Option zu sortieren. z.B. wenn Sie (aus irgendeinem Grund) wollte eine Liste von Zahlen heapify nach ihren Sinus:

   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. Das heapq Modul ist in reinem Python implementiert. Sie könnten kopieren Sie sie einfach in Ihr Arbeitsverzeichnis und die entsprechenden Bits ändern. Von einem kurzen Blick, würden Sie haben siftdown () und siftup () ändern, und möglicherweise nlargest und nsmallest, wenn Sie sie benötigen.