A volte durante i contest di programmazione, ecc., Abbiamo bisogno di una semplice implementazione funzionante della coda di priorità minima con il tasto di riduzione per implementare l’algoritmo di Dijkstra ecc. Io uso spesso il set <pair > e un array (ID di mapping -> valore_chiave ) insieme per raggiungere questo objective.
L’aggiunta di un elemento al set richiede tempo O (log (N)). Per build una coda di priorità su N elementi, li aggiungiamo semplicemente uno alla volta nel set. Questo richiede tempo O (N log (N)) in totale.
L’elemento con key_value minimo è semplicemente il primo elemento dell’insieme. Il rilevamento dell’elemento più piccolo richiede O (1) tempo. La rimozione richiede tempo O (log (N)).
Per verificare se alcuni ID = k si trovano nell’insieme, per prima cosa cerchiamo key_value = v_k nell’array e poi cerchiamo l’elemento (v_k, k) nel set. Questo richiede O (log (N)) tempo.
Per modificare il valore_chiave di alcuni ID = k da v_k a v_k ‘, per prima cosa cerchiamo key_value = v_k nell’array, quindi cerchiamo l’elemento (v_k, k) nel set. Quindi rimuoviamo quell’elemento dal set e quindi inseriamo l’elemento (v_k ‘, k) nel set. Quindi aggiorniamo anche l’array. Questo richiede O (log (N)) tempo.
Sebbene l’approccio di cui sopra funzioni, la maggior parte dei libri di testo consiglia di utilizzare gli heap binari per implementare le code di priorità, poiché il tempo di creazione degli heap binari è solo O (N). Ho sentito che esiste una struttura di dati della coda di priorità incorporata in STL di C ++ che utilizza gli heap binari. Tuttavia, non sono sicuro di come aggiornare il valore_chiave per quella struttura dati.
Qual è il modo più semplice ed efficiente di utilizzare la coda di priorità minima con l’aggiornamento chiave in C ++?
Bene, come già affermato da Darren, std::priority_queue non ha mezzi per diminuire la priorità di un elemento e né la rimozione di un elemento diverso dal minuto corrente. Ma lo standard std::priority_queue non è altro che un semplice adattatore contenitore attorno a un std::vector che utilizza le funzioni di heap std da std::push_heap , std::pop_heap e std::make_heap ). Quindi per Dijkstra (dove è necessario un aggiornamento prioritario) di solito lo faccio da solo e uso un semplice std::vector .
Una spinta è quindi solo l’operazione O (log N)
vec.push_back(item); std::push_heap(vec.begin(), vec.end());
Ovviamente per build una coda di nuovo da N elementi, non li spingiamo tutti usando questa operazione di O (log N) (facendo il tutto O (Nlog N)) ma li inseriamo tutti nel vettore seguito da una semplice O (N)
std::make_heap(vec.begin(), vec.end());
L’elemento min è un semplice O (1)
vec.front();
Un pop è la semplice sequenza O (log N)
std::pop_heap(vec.begin(), vec.end()); vec.pop_back();
Finora questo è solo ciò che std::priority_queue solito fa sotto il cofano. Ora per cambiare la priorità di un object, dobbiamo solo cambiarlo (tuttavia può essere incorporato nel tipo di elemento) e rendere nuovamente la sequenza un heap valido
std::make_heap(vec.begin(), vec.end());
So che questa è un’operazione O (N), ma d’altra parte rimuove qualsiasi necessità di tenere traccia della posizione di un object nell’heap con una struttura dati aggiuntiva o (ancora peggio) un aumento del tipo di elementi. E la penalizzazione delle prestazioni rispetto a un aggiornamento prioritario logaritmico non è in pratica quella significativa, considerando la facilità d’uso, la memoria compatta e lineare dell’uso di std::vector (che influenza anche il runtime) e il fatto che spesso lavoro con grafici che avere piuttosto pochi bordi (lineari nel conteggio dei vertici) comunque.
In ogni caso, potrebbe non essere il modo più veloce, ma sicuramente il più semplice.
EDIT: Oh, e dal momento che la libreria standard utilizza max-heap, è necessario utilizzare un equivalente a > per confrontare le priorità (tuttavia si ottengono dagli elementi) anziché l’operatore < predefinito.
Sebbene la mia risposta non risponda alla domanda originale, penso che potrebbe essere utile per le persone che raggiungono questa domanda quando provano ad implementare l’algoritmo Dijkstra in C ++ / Java (come me), qualcosa che è stato commentato dall’OP,
priority_queue in C ++ (o PriorityQueue in Java) non fornisce un’operazione decrease-key , come detto in precedenza. Un bel trucco per l’utilizzo di tali classi quando si implementa Dijkstra sta usando “cancellazione pigra”. Il ciclo principale dell’algoritmo Dijkstra estrae il nodo successivo da elaborare dalla coda di priorità e analizza tutti i nodes adiacenti, modificando infine il costo del percorso minimo per un nodo nella coda di priorità. Questo è il punto in cui decrease-key solito è necessario decrease-key per aggiornare il valore di quel nodo.
Il trucco non è affatto cambiarlo . Invece, una “nuova copia” per quel nodo (con il suo nuovo costo migliore) viene aggiunta alla coda di priorità. Avendo un costo inferiore, quella nuova copia del nodo verrà estratta prima della copia originale nella coda, quindi verrà elaborata in precedenza.
Il problema con questa “cancellazione pigra” è che la seconda copia del nodo, con il costo cattivo più alto, verrà alla fine estratta dalla coda di priorità. Ma ciò si verificherà sempre dopo l’elaborazione della seconda copia aggiunta, con un costo migliore. Quindi, la prima cosa che il loop Dijkstra principale deve fare quando si estrae il nodo successivo dalla coda di priorità è controllare se il nodo è già stato visitato (e conosciamo già il percorso più breve). È in quel preciso momento in cui faremo la “cancellazione pigra” e l’elemento deve essere semplicemente ignorato.
Questa soluzione avrà un costo sia in memoria che in tempo, perché la coda prioritaria sta memorizzando “elementi morti” che non abbiamo rimosso. Ma il costo reale sarà piuttosto piccolo, e programmare questa soluzione è, IMHO, più facile di qualsiasi altra alternativa che cerca di simulare l’operazione con il decrease-key mancante.
Non penso che la class std::priority_queue consenta un’efficiente implementazione delle operazioni di stile a decrease-key .
Ho eseguito il rollover della mia struttura dati basata su heap binario che supporta questo, in modo basale su linee molto simili a ciò che hai descritto per la coda di priorità basata su std::set che hai:
value che memorizza gli elementi di pair e un array che mappa ID -> heap_index . All’interno delle routine heap heapify_up, heapify_down ecc., È necessario assicurarsi che l’array di mapping sia mantenuto sincronizzato con la posizione heap corrente degli elementi. Ciò aggiunge un overhead aggiuntivo di O(1) . O(N) secondo l’algoritmo standard qui descritto. O(1) . ID è attualmente nell’heap richiede solo una ricerca O(1) nell’array di mapping. Ciò consente anche a O(1) occhiata all’elemento corrispondente a qualsiasi ID . Decrease-key richiede una ricerca O(1) nella matrice di mapping seguita da un aggiornamento di O(log(N)) heapify_up, heapify_down tramite heapify_up, heapify_down . O(log(N)) come è un object uscente dall’heap. Quindi in modo asintotico il runtime è migliorato per alcune delle operazioni rispetto alla struttura dei dati basata su std::set . Un altro importante miglioramento è che gli heap binari possono essere implementati su un array, mentre gli alberi binari sono contenitori basati su nodes. La localizzazione aggiuntiva dei dati dell’heap binario di solito si traduce in un runtime migliorato.
Alcuni problemi con questa implementazione sono:
ID dell’object intero. ID degli articoli, partendo da zero (altrimenti la complessità spaziale dell’array di mapping esplode!). Potresti riuscire a superare questi problemi se mantieni una tabella hash di mapping, piuttosto che un array di mapping, ma con un po ‘più di overhead di runtime. Per il mio uso, gli ID interi sono sempre stati sufficienti.
Spero che questo ti aiuti.