10
Esiste una coda heap/priorità Fibonacci disponibile per Haskell? (? O anche un uno asintoticamente meglio) ho trovato un elenco di varie implementazioni coda di priorità in this question, ma non riuscivo a trovare se qualcuno di loro soddisfa il tempo di esecuzione ammortizzato dei cumuli di Fibonacci:Esiste una coda di priorità basata su heap Fibonacci per Haskell?
- Trova-minimo è O (1) tempo ammortizzato.
- Le operazioni di inserimento, riduzione di chiave e unione (lavoro) sono O (1) tempo ammortizzato.
- Le operazioni di eliminazione e cancellazione minima sono O (log n) tempo ammortizzato.
Vedere the comparison of theoretic bounds.
È possibile che non esista alcun codice di produzione, poiché i fattori costanti generalmente rendono gli heap di Fibonacci più lenti degli heap binomiali per i set di dati di dimensioni ragionevoli, nonostante il vantaggio teorico asintotico. –
@OliCharlesworth Interessante, potresti dare una stima approssimativa per quali dimensioni gli heap di Fibonacci diventano vantaggiosi? –
TBH, questo è un po 'fuori dalla mia area; Ho letto solo di questi svantaggi (vedi per esempio [CLRS] (http://en.wikipedia.org/wiki/CLRS)). Non citatemi sopra;) –