Come posso implementare la funzionalità di chiave decrescente nell'heapq di Python?

Question

So che è possibile realizzare funzionalità di tasto decremento in O (log n) ma non so come?

Answer 1

Per implementare efficacemente "tasto di riduzione", è necessario accedere alla funzionalità "decrementa questo elemento E scambia questo elemento con un figlio finché non viene ripristinata la condizione dell'heap". In heapq.py, si chiama _siftdown (e allo stesso modo _siftup per INcrementing). Quindi la buona notizia è che le funzioni ci sono ... la cattiva notizia è che i loro nomi iniziano con un trattino basso, che indica che sono considerati "dettagli di implementazione interna" e non dovrebbero essere accessibili direttamente dal codice dell'applicazione (la prossima versione del la libreria standard potrebbe cambiare le cose e rompere il codice usando tali "interni").

Sta a voi decidere se si vuole ignorare l'avviso leading- _, utilizzare O (N) heapify invece di O (log N) vagliatura, o reimplementare alcune o tutte le funzionalità di heapq per rendere le primitive vagliatura " esposti come parti pubbliche dell'interfaccia ". Poiché la struttura dei dati di heapq è documentata e pubblica (solo una lista), penso che la scelta migliore sia probabilmente una reimplementazione parziale: copiare le funzioni di setacciamento da heapq.py nel codice dell'applicazione, in sostanza.

Answer 2

Immaginate di utilizzare un heap come coda di priorità, in cui vi sono un sacco di attività rappresentate da stringhe e ogni attività ha una chiave. Per concretezza, guarda: task_list = [[7,"do laundry"], [3, "clean room"], [6, "call parents"]] dove ogni attività in task_list è una lista con una priorità e una descrizione. Se si esegue heapq.heapify(task_list), si ottiene l'array per mantenere invariato l'heap. Tuttavia, se si desidera modificare la priorità di "do laundry" su 1, non si ha modo di sapere dove "do laundry" si trova nell'heap senza una scansione lineare attraverso l'heap (quindi non può fare diminuire_key in tempo logaritmico) . Nota: decrease_key(heap, i, new_key) richiede di conoscere l'indice del valore da modificare nell'heap.

Anche se si mantiene un riferimento a ciascun sottolista e si modifica effettivamente la chiave, non è ancora possibile farlo nel tempo di registrazione. Dal momento che una lista è solo un riferimento a un gruppo di oggetti mutabili, puoi provare a fare qualcosa come ricordare l'ordine originale dell'attività: (in questo caso "fare il bucato" era la 0a attività nel tuo originale task_list):

task_list = [[7, "do laundry"], [3, "clean room"], [6, "call parents"]] 
task_list_heap = task_list[:] # make a non-deep copy 
heapq.heapify(task_list_heap) 
# at this point: 
# task_list = [[7, 'do laundry'], [3, 'clean room'], [6, 'call parents']] 
# task_list_heap = [3, 'clean room'], [7, 'do laundry'], [6, 'call parents']] 
# Change key of first item of task_list (which was "do laundry") from 7 to 1. 
task_list[0][0] = 1 
# Now: 
# task_list = [[1, 'do laundry'], [3, 'clean room'], [6, 'call parents']] 
# task_list_heap = [3, 'clean room'], [1, 'do laundry'], [6, 'call parents']] 
# task_list_heap violates heap invariant at the moment 

Tuttavia, è ora necessario chiamare heapq._siftdown(task_list_heap, 1) per mantenere l'invariante heap in tempo di log (heapq.heapify è tempo lineare), ma purtroppo non si conosce l'indice di "fare il bucato" in task_list_heap (il heap_index in questo caso è 1).

Quindi dobbiamo implementare il nostro heap per tenere traccia dello heap_index di ciascun oggetto; ad esempio, avere un list (per l'heap) e un dict mappare ogni oggetto al suo indice nell'heap/list (che viene aggiornato quando le posizioni heap vengono scambiate aggiungendo un fattore costante a ogni scambio). Puoi leggere heapq.py e implementare te stesso come la procedura è semplice; tuttavia, altri hanno già implementato questo tipo di HeapDict.

Answer 3

Il heapq documentation ha una voce su esattamente come fare questo.

Tuttavia, ho scritto un pacchetto heap che fa esattamente questo (è un wrapper intorno a heapq).Quindi, se avete pip o easy_install si potrebbe fare qualcosa di simile

pip install heap 

Poi, nel tuo codice di scrittura

from heap.heap import heap 

h = heap() 

h['hello'] = 4 # Insert item with priority 4. 

h['hello'] = 2 # Update priority/decrease-key has same syntax as insert. 

E è abbastanza nuovo, però, quindi potrebbe essere pieno di bug.

Answer 4

La chiave di riduzione è un'operazione indispensabile per molti algoritmi (Algoritmo di Dijkstra, A *, OPTICS), mi chiedo perché la coda di priorità incorporata di Python non la supporti.

Sfortunatamente, non ero in grado di scaricare il pacchetto di math4tots.

Ma, sono stato in grado di trovare l'implementazione this di Daniel Stutzbach. Ha funzionato perfettamente per me con Python 3.5.