Come posso implementare una coda con priorità doppia terminata con O(log(n)) complessità di inserimento, trovare min e trovare le operazioni massime?
Stavo pensando di usare un albero nero rosso, ma è un po 'complicato. C'è un'alternativa più semplice?
Ho anche sentito parlare di un heap a doppio attacco, ma la complessità di trovare o eliminare il minimo e il massimo sembra essere lineare e non logaritmica.
Ecco cosa ho fatto per un'implementazione free-list con allocatore di blocchi che necessitava di una coda con priorità doppia:
Questo produce:
Poiché quelle erano le uniche operazioni di cui avevo bisogno per la mia particolare applicazione, questa era praticamente la migliore struttura dati possibile. Anche se avevi bisogno di altre operazioni con le code di priorità (come cambiare le priorità, ecc.) Quasi tutto sarebbe ancora O (log n) worst case a causa dell'albero rosso-nero.
Il motivo per cui ottieni O (1) sia per find-min / max che delete-min / max è che hai tenuto traccia dell'elemento minimo e massimo durante l'inserimento, così puoi immediatamente trovarlo, eliminando O (log n) per la ricerca. Quindi l'algoritmo albero rosso-nero garantisce le operazioni O (1) per riequilibrare l'albero dopo che l'elemento è stato rimosso. (Questa è una proprietà ben nota e molto importante degli alberi rosso-neri. Questo non sarebbe il caso della maggior parte degli altri alberi di ricerca binari, come gli alberi AVL, che richiedono operazioni O (log n) durante il ribilanciamento.)
(Dopo più di un anno, sono tornato quasi a caso in questa domanda, quindi ho deciso di rispondere alla mia domanda!)
Dopo alcune ricerche, ho finito per avere la sensazione che la struttura dei dati più intuitiva e appropriata (in realtà non ho fatto test di benchmark del mondo reale) per implementare una coda di priorità a doppio attacco è in realtà il min-max heap , che ha il suo proprio articolo di Wikipedia , che Ho cercato di migliorare in base al documento originale del 1986 ( di Atkinson, Sack, Santoro e Strothotte), ma per mancanza di tempo non ho finito di scrivere le descrizioni di tutte le sue operazioni. A proposito, sentiti libero di aiutarmi!
Come ho spiegato nell'articolo di Wikipedia:
...it provides constant time retrieval and logarithmic time removal of both the minimum and maximum elements in it.
Se vuoi conoscere maggiori dettagli sulla complessità temporale delle operazioni, dai un'occhiata al documento originale.
Ho anche implementato un min-max heap in Python, per quelli di voi che stanno cercando un programma concreto. Sembra essere l'implementazione più affidabile che ho trovato finora, ma non escludo comunque gli errori, anche se ho anche creato dei test per questo.
https://github.com/nbro/ands/blob/master/ands/ds/MinMaxHeap.py
Si noti che questo programma fa parte di un modulo, cioè non si può semplicemente copiare il codice ed eseguirlo e qualcosa funziona. Per favore, leggi README del progetto a cui ti sto collegando per maggiori informazioni su come usare quel modulo.
Leggi altre domande sui tag algorithms implementations