Gli heap di Fibonacci o le code Brodal sono utilizzati in pratica ovunque?

Question

Gli heap di Fibonacci sono utilizzati in pratica ovunque? Ho dato un'occhiata a SO e ho trovato risposte a domande correlate (vedi sotto), ma nulla in realtà risponde alla domanda.

1. There are good implementations of Fibonacci heaps out there, including in standard libraries such as Boost C++. Il fatto che queste librerie contengono cumuli di Fibonacci suggerisce essere il fatto che essi devono essere utili in qualche luogo.
2. Sappiamo che alcune condizioni devono essere soddisfatte affinché un heap di Fibonacci sia più veloce nella pratica: "to benefit from Fibonacci heaps in practice, you have to use them in an application where decrease_keys are incredibly frequent"; "For the Fibonacci Heap to really shine, you need either of the following cases: a) Expensive comparisons: Fib Heaps minimize the number of comparisons required to organize the data. b) The majority of operations is updateKey/insert/delete. As Fibonacci Heaps 'group' the updates together until the next extractMin, the larger the 'batch', the more efficient it gets."
3. There is a data structure called a "Brodal Queue" which I'm not sure I'd heard of before that seems to have time complexity behaviors at least as good as Fibonacci heaps.Here è un bel tavolo con un confronto di complessità temporali per varie operazioni per diverse varietà di cumuli.
4. Su a question about whether there are any applications of Fibonacci or binomial heaps, i rispondenti hanno fornito solo esempi di cumuli binomiali.

Answer 1

In base alle mie conoscenze, non esistono applicazioni principali che utilizzano effettivamente heap Fibonacci o code Brodal.

Gli heap di Fibonacci sono stati inizialmente progettati per soddisfare un'esigenza teorica piuttosto che pratica: accelerare asintoticamente l'algoritmo dei percorsi più brevi di Dijkstra. La coda Brodal (e la relativa struttura dei dati funzionali) sono state progettate allo stesso modo per soddisfare le garanzie teoriche, in particolare, per rispondere a una lunga e aperta domanda sull'opportunità di far corrispondere i limiti temporali di un heap di Fibonacci con le garanzie del caso peggiore piuttosto che le garanzie ammortizzate . In questo senso, le strutture dati non sono state sviluppate per soddisfare esigenze pratiche, ma piuttosto per far avanzare la nostra comprensione teorica dei limiti di efficienza algoritmica. Per quanto ne so, non ci sono algoritmi presenti in cui sarebbe effettivamente meglio usare una coda Brodal su un heap di Fibonacci.

Come altre risposte hanno notato, i fattori costanti nascosti in un heap di Fibonacci o coda di Brodal sono molto alti. Hanno bisogno di molti puntatori cablati in molte liste concatenate complicate e, di conseguenza, hanno una località di riferimento assolutamente terribile, soprattutto rispetto ad un heap binario standard. Ciò significa che è probabile che nella pratica si verifichino risultati peggiori a causa degli effetti di memorizzazione nella cache, a meno che non si disponga di algoritmi che richiedono un numero colossale di operazioni con il tasto di riduzione. Ci sono alcuni casi in cui questo emerge (le risposte collegate parlano di alcuni di essi, ad esempio), ma li trattano come circostanze altamente specializzate piuttosto che casi d'uso comuni. Se stai lavorando su grafici di grandi dimensioni, è più comune utilizzare altre tecniche per migliorare l'efficienza, ad esempio utilizzando algoritmi di approssimazione per il problema in questione, euristiche migliori o algoritmi che utilizzano proprietà specifiche dei dati sottostanti.

Spero che questo aiuti!