Applicazioni del mondo reale di heap binari e heap di Fibonacci

Question

Quali sono le applicazioni del mondo reale degli heap di Fibonacci e degli heap binari? Sarebbe bello poter condividere qualche istanza quando lo hai usato per risolvere un problema.

Modifica: Anche gli heap binari aggiunti. Curioso di sapere.

Answer 1

Raramente ne useresti uno nella vita reale. Credo che lo scopo dell'heap di Fibonacci fosse quello di migliorare il tempo di esecuzione asintotico dell'algoritmo di Dijkstra. Potrebbe darti un miglioramento per input molto grandi, ma la maggior parte delle volte, un semplice heap binario è tutto ciò di cui hai bisogno.

Da Wiki:

Sebbene il tempo totale di una sequenza di operazioni iniziano una struttura vuota è delimitata dai limiti indicati sopra, alcuni (pochissimi) operazioni nella sequenza può Take molto lungo per completare (in particolare eliminare e cancellare minimo hanno lineare tempo di esecuzione nel peggiore dei casi). Per , questo heap di Fibonacci e altre strutture di dati ammortizzate potrebbero non essere appropriato per i sistemi in tempo reale.

L'heap binario è una struttura di dati che può essere utilizzata per trovare rapidamente il valore massimo (o minimo) in un insieme di valori. Viene utilizzato nell'algoritmo di Dijkstra (percorso più breve), nell'algoritmo di Prim (albero di spanning minimo) e nella codifica di Huffman (compressione dei dati).

Answer 2

Code di priorità sono generalmente implementati come cumuli, per esempio: http://download.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html

calcolando il top N elementi da un enorme set di dati può essere fatto in modo efficiente utilizzando cumuli binari (ad esempio query di ricerca in un sito web su larga scala) .

Answer 3

Non si può dire degli heap di Fibonacci, ma gli heap binari vengono utilizzati nelle code di priorità. Le code prioritarie sono ampiamente utilizzate nei sistemi reali. Un esempio noto è la pianificazione dei processi nel kernel. Il processo con la priorità più alta viene preso per primo. Ho usato le code di priorità nel partizionamento dei set. Il set che ha i membri massimi doveva essere preso prima per il partizionamento.

Answer 4

Nella maggior parte degli scenari, si deve scegliere in base alla complessità di:

• inserimento
• elementi che trovano i

E i soliti sospetti sono:

• BST: log(n) inserisci e trova
• lista collegata: O(1) inserto e O(n) trovare
• mucchio:
  • O(1) inserto
    • media per heap binario, vedi: https://stackoverflow.com/a/29548834/895245)
    • ammortizzati per Fibonacci. Questo è più forte della media, più debole del peggiore dei casi.
  • O(1) trovare per il primo elemento unico, O(n) in generale
    • caso peggiore per l'heap binario
    • ammortizzato per Fibonacci

C'è anche lo Brodal queue e altri heap che raggiungono il O(1) caso peggiore, ma richiede il valore di even larger queues rispetto a Fibonacci per meritarlo.

Quindi, se l'algoritmo deve solo "trovare" il primo elemento e fare molti inserimenti, gli heap sono una buona scelta.

Come già menzionato, questo è il caso di Dijkstra.