Come rendere heapq valutare l'heap di un attributo specifico?

Question

Desidero tenere un mucchio di oggetti, non solo numeri. Avranno in loro un attributo intero che l'heap può ordinare. Il modo più semplice per usare gli heap in python è heapq, ma come faccio a ordinarlo per ordinare un attributo specifico quando si usa heapq?

Answer 1

heapq sorta oggetti allo stesso modo list.sort fa, quindi basta definire un metodo __cmp__() all'interno della definizione di classe, che si metterà a confronto a un'altra istanza della stessa classe:

def __cmp__(self, other): 
    return cmp(self.intAttribute, other.intAttribute) 

Lavori in Python 2.x.

In uso 3.x:

def __lt__(self, other): 
    return self.intAttribute < other.intAttribute 

Answer 2

Sfortunatamente, non è possibile, anche se questa è una caratteristica spesso richiesta.

Un'opzione consisterebbe nell'inserire tuple (chiave, valore) nell'heap. Tuttavia, ciò non funzionerà se i valori generano un'eccezione quando confrontati (saranno confrontati nel caso di un legame tra le chiavi).

Una seconda opzione sarebbe quella di definire un metodo __lt__ (minore di) nella classe che utilizzerà l'attributo appropriato per confrontare gli elementi per l'ordinamento. Tuttavia, ciò potrebbe non essere possibile se gli oggetti sono stati creati da un altro pacchetto o se è necessario confrontarli in modo diverso altrove nel programma.

Una terza opzione consiste nell'utilizzare la classe sortedlist dal modulo blist (dichiarazione di non responsabilità: sono l'autore). Il costruttore per accetta un parametro key che consente di specificare una funzione per restituire la chiave di ordinamento di un elemento, simile al parametro key di list.sort e sorted.

Answer 3

Secondo l'esempio dal documentation, è possibile utilizzare tuple, e sarà ordinare dal primo elemento della tupla:

>>> h = [] 
>>> heappush(h, (5, 'write code')) 
>>> heappush(h, (7, 'release product')) 
>>> heappush(h, (1, 'write spec')) 
>>> heappush(h, (3, 'create tests')) 
>>> heappop(h) 
(1, 'write spec') 

Così se non si desidera (o non si può?) fare un metodo __cmp__, è possibile estrarre manualmente la chiave di ordinamento all'ora push.

Si noti che se i primi elementi in una coppia di tuple sono uguali, verranno confrontati ulteriori elementi. Se questo non è ciò che desideri, devi assicurarti che ogni primo elemento sia unico.