La struttura dati Fibonacci heap ha la parola "Fibonacci" nel nome, ma nulla nella struttura dati sembra utilizzare i numeri di Fibonacci. Secondo l'articolo di Wikipedia:Perché un cumulo di Fibonacci è chiamato mucchio di Fibonacci?
Il nome dell'heap di Fibonacci deriva dai numeri di Fibonacci utilizzati nell'analisi del tempo di esecuzione.
Come sorgono questi numeri di Fibonacci nell'heap di Fibonacci?
Il cumulo di Fibonacci è costituito da una serie di alberi più piccoli, ordinati per heap, di "ordini" diversi che rispettano certi vincoli strutturali. La sequenza di Fibonacci deriva dal fatto che questi alberi sono costruiti in modo tale che un albero di ordine n abbia almeno F n + 2 nodi, dove F n + 2 è il numero (n + 2) di Fibonacci.
Per capire perché questo risultato è vero, iniziamo osservando come vengono costruiti gli alberi nell'heap di Fibonacci. Inizialmente, ogni volta che un nodo viene inserito in un heap di Fibonacci, viene inserito in un albero di ordine 0 che contiene solo quel nodo. Ogni volta che un valore viene rimosso dall'heap di Fibonacci, alcuni degli alberi nell'heap di Fibonacci vengono coalizzati insieme in modo che il numero di alberi non cresca troppo.
Quando si uniscono gli alberi, l'heap di Fibonacci combina solo alberi dello stesso ordine. Per combinare due alberi di ordine n in un albero di ordine n + 1, l'heap di Fibonacci prende quello dei due alberi con un valore di radice maggiore dell'altro, quindi rende quell'albero un figlio dell'altro albero. Una conseguenza di questo fatto è che gli alberi di ordine n hanno sempre n bambini.
L'attrazione principale dell'heap di Fibonacci è che supporta efficientemente la chiave di decremento (in O (1) ammortizzato). Per supportare questo, l'heap di Fibonacci implementa il tasto di riduzione come segue: per diminuire la chiave di un valore memorizzato in qualche nodo, quel nodo viene tagliato dall'albero padre e trattato come il proprio albero separato. Quando ciò accade, l'ordine del suo vecchio nodo genitore viene diminuito di uno. Ad esempio, se un albero di ordine 4 ha un bambino tagliato da esso, si riduce a un albero di ordine 3, il che ha senso perché l'ordine di un albero dovrebbe essere il numero di bambini che contiene.
Il problema con questo è che se troppi alberi vengono troncati dallo stesso albero, potremmo avere un albero con un grande ordine ma che contiene un numero molto piccolo di nodi. Le garanzie temporali di un heap di Fibonacci sono possibili solo se gli alberi con grandi ordini contengono un numero enorme di nodi e se possiamo solo tagliare tutti i nodi che vorremmo dagli alberi potremmo facilmente entrare in una situazione in cui un albero con un ordine enorme contiene solo un piccolo numero di nodi.
Per risolvere questo problema, gli heap di Fibonacci richiedono un requisito - se si tagliano due bambini da un albero, è necessario tagliare a sua volta quell'albero dal relativo genitore. Ciò significa che gli alberi che formano un heap di Fibonacci non verranno danneggiati troppo gravemente dal tasto di diminuzione.
E ora possiamo ottenere la parte sui numeri di Fibonacci. A questo punto, possiamo dire quanto segue sugli alberi in un heap di Fibonacci:
Quindi ora possiamo chiedere - quali sono gli alberi più piccoli che è possibile realizzare in base a questi presupposti?
Proviamo alcuni esempi. C'è solo una possibile albero di ordine 0, che è un solo un singolo nodo:
Smallest possible order 0 tree: *
Il più piccolo albero possibile di ordine 1 avrebbe dovuto essere almeno un nodo con un bambino. Il bambino più piccolo possibile che potremmo fare è un singolo nodo con il più piccolo ordine-0 albero come un bambino, che è questo albero:
Smallest possible order 1 tree: *
|
*
cosa circa il più piccolo albero di ordine 2? Questo è dove le cose si fanno interessanti. Quest'albero deve certamente avere due figli, e sarebbe formato unendo insieme due alberi di ordine 1. Di conseguenza, l'albero inizialmente avrebbe due figli: un albero di ordine 0 e un albero di ordine 1. Ma ricorda: possiamo tagliare i bambini dagli alberi dopo averli uniti! In questo caso, se tagliamo via il bambino dell'albero di ordine 1, saremmo partiti con un albero con due figli, che sono entrambi alberi di ordine 0:
Smallest possible order 2 tree: *
/\
* *
Come su ordine 3? Come in precedenza, questo albero sarebbe stato realizzato unendo due alberi di ordine 2. Avremmo quindi cercato di tagliare il maggior numero possibile di sottoalberi di questo albero di ordine 3. Quando viene creato, l'albero ha sottoalberi degli ordini 2, 1 e 0. Non possiamo tagliare via l'albero 0 dell'ordine, ma possiamo tagliare un singolo figlio dall'ordine 2 e ordinare 1 albero. Se facciamo questo, siamo lasciati con un albero con tre figli, uno di ordine 1, e due di ordine 2:
Smallest possible order 3 tree: *
/|\
* * *
|
*
Ora possiamo individuare un modello. Il più piccolo ordine possibile (n + 2) albero si formerebbe come segue: inizia creando un albero normale (n + 2), che ha figli di ordini n + 1, n, n - 1, ..., 2 , 1, 0. Quindi, rendi gli alberi il più piccoli possibile tagliando loro i nodi senza tagliare due bambini dallo stesso nodo. Questo lascia un albero con figli di ordini n, n - 2, ..., 1, 0 e 0.
Possiamo ora scrivere una relazione di ricorrenza per provare a determinare quanti nodi ci sono in questi alberi. Se facciamo questo, si ottiene il seguente, dove NC (n) rappresenta il più piccolo numero di nodi che potrebbero essere in un albero di ordine n:
NC(0) = 1
NC(1) = 2
NC(n + 2) = NC(n) + NC(n - 1) + ... + NC(1) + NC(0) + NC(0) + 1
Qui, gli ultimi +1 conti per il nodo radice stessa .
Se ci espandiamo questi termini, otteniamo la seguente:
NC(0) = 1
NC(1) = 2
NC(2) = NC(0) + NC(0) + 1 = 3
NC(3) = NC(1) + NC(0) + NC(0) + 1 = 5
NC(4) = NC(2) + NC(1) + NC(0) + NC(0) + 1 = 8
Se si noterà, questo è esattamente la serie di Fibonacci compensato da due posizioni. In altre parole, ognuno di questi alberi deve avere almeno F n + 2 nodi in cui F n + 2 è il numero (n + 2) n Fibonacci.
Quindi perché si chiama un heap di Fibonacci? Poiché ogni albero di ordine n deve avere almeno F n + 2 nodi in esso!
Se siete curiosi, the original paper on Fibonacci heaps ha le immagini di questi piccoli alberi possibili. È davvero carino da vedere!
Spero che questo aiuti!
Voglio dare una spiegazione intuitiva che io stesso ho avuto un "Aha!" momento con.
Le strutture ad albero raggiungono i runtime O (log n) perché sono in grado di memorizzare un numero esponenziale di articoli in termini di altezze. Gli alberi binari possono memorizzare 2^h, gli alberi tri-nari possono memorizzare 3^h e così via per x^h come caso generico.
Può essere inferiore a 2? Certo che può! Finché x> 1, otteniamo comunque i runtime dei log e la possibilità di memorizzare un numero esponenzialmente elevato di articoli per la sua altezza. Ma come costruiamo un albero del genere? L'heap di Fibonacci è una struttura di dati in cui x ≈ 1.62 o Golden Ratio. Ogni volta che incontriamo la sezione aurea, ci sono numeri di Fibonacci in agguato da qualche parte ...
L'heap di Fibonacci è in realtà una foresta di alberi. Dopo un processo chiamato "consolidamento", ognuno di questi alberi contiene un numero distinto di oggetti che sono poteri esatti di 2. Ad esempio, se il tuo heap di Fibonacci ha 15 elementi, avrebbe 4 alberi che contengono 1, 2, 4 e 8 articoli, rispettivamente, cercando in questo modo:
dettagli del processo di "consolidamento" non è rilevante, ma in sostanza si mantiene sostanzialmente unioning alberi nella foresta di stesso grado fino a quando tutti gli alberi hanno gradi distinti (provare una cool visualization di vedere come vengono costruiti questi alberi). Siccome puoi scrivere n qualsiasi come somma dei poteri esatti di 2, è facile immaginare come sarebbero stati gli alberi consolidati per l'heap di Fibonacci per ogni n.
OK, finora non vediamo ancora alcuna connessione diretta ai numeri di Fibonacci. Dove vengono in foto? In realtà appaiono in un caso molto speciale e questa è anche la chiave del perché l'heap di Fibonacci può offrire il tempo O (1) per l'operazione DECREASE-KEY. Quando diminuiamo una chiave, se la nuova chiave è ancora più grande della chiave genitore, non è necessario fare nient'altro perché la proprietà min-heap non viene violata. Ma se non lo è, non possiamo lasciare il bambino più piccolo sepolto sotto un genitore più grande e quindi dobbiamo tagliare la sottostruttura e ricavarne un nuovo albero. Ovviamente non possiamo continuare a farlo per ogni eliminazione, perché altrimenti ci ritroveremo con alberi troppo alti e non più dotati di elementi esponenziali, il che significa che non ci sarà più tempo O (log n) per l'operazione di estrazione. Quindi la domanda è: quale regola possiamo impostare in modo che l'albero abbia ancora elementi esponenziali per la sua altezza? L'intuizione intelligente è questo:
We will allow each parent to loose up to one child. If there is a subsequent attempt to remove another child from same parent then we will cut that parent also out of that tree and put it in root list as tree of 1.
Sopra regola assicura che gli alberi hanno ancora elementi esponenziali per la sua altezza, anche nel caso peggiore. Qual è il caso peggiore? Il caso peggiore si verifica quando facciamo perdere a ogni genitore un figlio. Se il genitore ha> 1 figlio, abbiamo la scelta di cui sbarazzarsi. In tal caso liberiamoci di un bambino con la sottostruttura più grande. Quindi, nel diagramma sopra, se lo fai per ogni genitore, avrai alberi delle dimensioni 1, 1, 2 e 3. Vedi uno schema qui? Solo per divertimento, aggiungi un nuovo albero di ordine 4 (cioè 16 elementi) nel diagramma sopra e indovina cosa rimarrebbe dopo aver eseguito questa regola per ciascun genitore: 5. Abbiamo una sequenza di Fibonacci qui!
Dato che la sequenza di Fibonacci è esponenziale, ogni albero conserva ancora il numero esponenziale di elementi e quindi riesce ad avere il runtime O (log n) per l'operazione EXTRACT-MIN. Tuttavia notare che DECREASE-KEY ora richiede solo O (1). Un'altra cosa interessante è che puoi rappresentare qualsiasi numero come somma dei numeri di Fibonacci.Ad esempio, 32 = 21 + 8 + 3, che significa che se hai bisogno di tenere 32 oggetti nell'heap di Fibonacci, puoi farlo usando 3 alberi che contengono rispettivamente 21, 8 e 3 voci. Tuttavia, il processo di "consolidamento" non produce alberi con numeri di nodi Fibonacci. Si verificano solo quando si verifica questo caso peggiore di DECREASE-KEY o DELETE.
Letture
Suppongo che il problema sia che non conosciamo la dimensione degli alberi, ma solo un'approssimazione in termini di classificazione. Se potessimo conoscere le dimensioni, potremmo unirle come nella codifica di Huffman e le cose andrebbero bene senza uccidere i genitori. Tuttavia, tenere traccia delle dimensioni degli alberi è troppo costoso. –
@ThomasAhle Proprio così. Gli heap di Fibonacci sono ottimizzati per consentire la riduzione delle chiavi di riduzione O (1) tagliando i nodi dai genitori e aggiornano solo le informazioni nel genitore diretto. Se si taglia un nodo dal suo genitore, è necessario aggiornare le dimensioni del sottostrato su tutti i suoi antenati, ma ciò richiede tempo Ω (log n) e interrompe il limite di tempo del tasto di riduzione O (1). – templatetypedef
Mi chiedo se qualcuno abbia provato a memorizzare un'approssimazione casuale delle dimensioni degli alberi. Quindi, quando si rimuove un bambino, l'algoritmo ridurrebbe le dimensioni dei suoi antenati con probabilità '1, 1/2, 1/4, ...', un po 'come un skiplist. Probabilmente non è né più semplice né più veloce nella pratica di un sacco di altri cumuli là fuori già. –