tas min 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 ya un module de heapq disponible dans le cadre de la distribution de python. Y at-il un moyen d'utiliser un comparateur personnalisé avec ce module? Sinon, quelqu'un a construit une autre commande min tas?

Answer 1

Oui, il y a un moyen. Définir une classe d'emballage qui implémente votre comparateur personnalisé, et utiliser une liste de ceux qui au lieu d'une liste de vos objets réels. C'est à peu près le meilleur il est tout en utilisant le module heapq, car il ne fournit aucune clé = ou cmp = arguments comme les fonctions de tri / méthodes font.

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 options (à part la suggestion de Devin Jeanpierre):

1. Décorez vos données avant d'utiliser le tas. Ceci est l'équivalent de l'option key= au 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 d'heapq est mis en oeuvre en python pure. Vous pouvez simplement le copier dans votre répertoire de travail et changer les bits correspondants. D'un rapide coup d'oeil, vous devez modifier siftdown () et siftup (), et peut-être nlargest et nsmallest si vous avez besoin.