heapq con predicato confronto personalizzato

Question

Sto cercando di creare un heap con un predicato di ordinamento personalizzato. Poiché i valori che entrano in esso sono di tipo "definito dall'utente", non posso modificare il loro predicato di confronto integrato.

C'è un modo per fare qualcosa di simile:

h = heapq.heapify([...], key=my_lt_pred) 
h = heapq.heappush(h, key=my_lt_pred) 

O meglio, ho potuto avvolgere le funzioni heapq nel mio contenitore in modo non ho bisogno di tenere passando il predicato.

Answer 1

In base allo heapq documentation, il modo in cui personalizzare l'ordine dell'heap consiste nell'assegnare ad ogni elemento dell'heap una tupla, con il primo elemento tuple che accetta normali confronti Python.

Le funzioni nel modulo heapq sono un po 'macchinose (poiché non sono orientate agli oggetti) e richiedono sempre che il nostro oggetto heap (un elenco heapificato) venga passato esplicitamente come primo parametro. Possiamo uccidere due piccioni con una fava creando una classe wrapper molto semplice che ci consentirà di specificare una funzione key e di presentare l'heap come un oggetto.

La classe sotto mantiene un elenco interno, in cui ogni elemento è una tupla, il primo elemento del quale è una chiave, calcolata al momento dell'inserimento dell'elemento utilizzando il parametro key, passato al mucchio esemplificazione:

# -*- coding: utf-8 -*- 
import heapq 

class MyHeap(object): 
    def __init__(self, initial=None, key=lambda x:x): 
     self.key = key 
     if initial: 
      self._data = [(key(item), item) for item in initial] 
      heapq.heapify(self._data) 
     else: 
      self._data = [] 

    def push(self, item): 
     heapq.heappush(self._data, (self.key(item), item)) 

    def pop(self): 
     return heapq.heappop(self._data)[1] 

Answer 2

Il heapq documentation suggerisce che gli elementi heap potrebbero essere le tuple in cui il primo elemento è la priorità e definisce l'ordinamento.

più pertinente alla tua domanda, tuttavia, è che la documentazione include una discussion with sample code di come si possa implementare le proprie funzioni heapq involucro per affrontare i problemi di stabilità sorta ed elementi con la stessa priorità (tra le altre questioni).

In breve, la loro soluzione è di avere ogni elemento nell'heapq una tripla con la priorità, un numero di voci e l'elemento da inserire. Il numero di voci garantisce che gli elementi con la stessa priorità siano ordinati nell'ordine in cui sono stati aggiunti all'heapq.

Answer 3

La limitazione con entrambe le risposte è che non consentono che i legami vengano trattati come legami. Nel primo, i legami vengono interrotti confrontando gli elementi, nel secondo confrontando l'ordine di input. È più veloce lasciare i legami come legami e se ce ne sono molti potrebbe fare una grande differenza. Sulla base di quanto sopra e sui documenti, non è chiaro se questo può essere ottenuto in heapq. Sembra strano che heapq non accetti una chiave, mentre le funzioni derivate da essa nello stesso modulo lo fanno.
P.S .: Se segui il collegamento nel primo commento ("possibile duplicato ...") c'è un altro suggerimento di definire le che sembra una soluzione.