min tas en python

Question

Je voudrais stocker un ensemble d'objets dans un tas min en définissant une fonction de comparaison personnalisée. Je vois qu'il y a un module heapq disponible dans le cadre de la distribution python. Est-il possible d'utiliser un comparateur personnalisé avec ce module? Sinon, quelqu'un d'autre a-t-il construit un tas min personnalisé?

Answer 1

Oui, il y a un moyen. Définissez une classe d'enveloppement qui implémente votre comparateur personnalisé et utilisez une liste de ceux-ci au lieu d'une liste de vos objets réels. C'est à peu près ce qu'il y a de mieux, tout en utilisant le module heapq, puisqu'il ne fournit aucun argument key = ou cmp = comme le font les fonctions/méthodes de tri.

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

Deux possibilités (à part la suggestion de Devin Jeanpierre):

1. vos données avant de Décore en utilisant le tas. C'est l'équivalent de l'option key= pour le tri. par exemple. si vous (pour une raison quelconque) voulait heapify une liste de numéros en fonction de leur 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. Le module heapq est mis en œuvre en python pur. Vous pouvez simplement le copier dans votre répertoire de travail et modifier les bits pertinents. D'un coup d'oeil rapide, vous devrez modifier siftdown() et siftup(), et éventuellement nlargest et nsmallest si vous en avez besoin.