miniatura|upright=1.05|alt=Exemplo dun montículo de Fibonacci.|Figura 1. Exemplo dun montículo de Fibonacci. Ten tres árbores de graos 0, 1 e 3. Tres vértices están marcados (en azul). Por tanto, o potencial do montículo é 9 (3 árbores + 2 × 3 vértices marcados).
En ciencias da computación, un montículo de Fibonacci é unha estrutura de datos para operacións de cola de prioridade, formada por unha colección de árbores ordenadas como montículos. Ten un tempo de execución amortizado mellor ca moitas outras estruturas de cola de prioridade, incluídos o montículo binario e o montículo binomial. Michael L. Fredman e Robert E. Tarjan desenvolveron os montículos de Fibonacci en 1984 e publicáronos nunha revista científica en 1987. Reciben o nome dos números de Fibonacci, que se usan na análise do seu tempo de execución.
A inserción, a consulta do mínimo, a diminución de chave dun nó localizado e a fusión teñen custo amortizado constante. Tanto o borrado do mínimo como o dun nó arbitrario previamente localizado teñen custo amortizado , onde é o tamaño do montículo. Partindo dunha estrutura baleira, unha secuencia de insercións e diminucións de chave e borrados do mínimo leva tempo , onde é o tamaño máximo. A cota correspondente para un montículo binario é . A vantaxe da cota do montículo de Fibonacci é maior cando predominan as diminucións de chave. A fusión tamén ten custo constante.
Usar montículos de Fibonacci mellora o tempo de execución asintótico de algoritmos que empregan colas de prioridade. Por exemplo, o algoritmo de Dijkstra e o algoritmo de Prim pódense facer correr en tempo .
Estrutura Un montículo de Fibonacci é unha colección de árbores que satisfán a propiedade do montículo mínimo: a chave dun fillo é sempre maior ou igual ca a do pai. Isto implica que a chave mínima está sempre na raíz dunha das árbores. A diferenza dos montículos binomial, a estrutura dun montículo de Fibonacci é máis flexible. As árbores non teñen unha forma prefixada e, no caso extremo, o montículo pode ter cada elemento nunha árbore separada. Esta flexibilidade permite executar algunhas operacións de forma preguiceira, aprazando o traballo para operacións posteriores. Por exemplo, fusionar montículos faise simplemente concatenando as dúas listas de árbores, e a operación de diminución de chave ás veces corta un nó do seu pai formando unha nova árbore.
Porén, nalgún momento hai que introducir orde no montículo para acadar o tempo de execución desexado. En particular, os graos dos nós (aquí grao significa número de fillos directos) mantéñense baixos: cada nó ten grao como máximo , onde , e o tamaño dunha subárbore con raíz nun nó de grao é polo menos , onde é o -ésimo número de Fibonacci. Isto conséguese coa regra de que se pode cortar como máximo un fillo de cada nó non raíz. Cando se corta un segundo fillo, o propio nó córtase do seu pai e convértese na raíz dunha nova árbore (véxase máis abaixo a demostración dos límites de grao). O número de árbores redúcese na operación de borrado do mínimo, onde as árbores se enlazan.
Como resultado da estrutura relaxada, algunhas operacións poden levar moito tempo mentres outras son moi rápidas. Para a análise amortizada, úsase o método do potencial: faise coma se as operacións moi rápidas levasen un pouco máis do que realmente levan. Ese tempo adicional combínase e réstase despois do tempo real das operacións lentas. A cantidade de tempo aforrada mídese cunha función de potencial. O potencial dun montículo de Fibonacci é
onde é o número de árbores e o número de nós marcados. Un nó está marcado se polo menos un dos seus fillos foi cortado desde que o nó se converteu en fillo doutro (todas as raíces están sen marcar). O tempo amortizado dunha operación é a suma do tempo real e veces a diferenza de potencial, onde é unha constante.
Así, a raíz de cada árbore ten unha unidade de tempo almacenada, que se pode usar despois para enlazar esa árbore con outra a tempo amortizado 0. Cada nó marcado ten dúas unidades de tempo: unha pódese usar para cortar o nó do seu pai e a outra queda almacenada como en calquera raíz.
Operacións Para permitir un borrado e unha concatenación rápidos, as raíces de todas as árbores enlázanse cunha lista ligada circular dobre. Cada nó mantén outra lista circular dobre cos seus propios fillos, separada da lista de raíces. Para cada nó mantense o seu número de fillos e se está marcado.
Atopar o mínimo Mantense un punteiro á raíz que contén a chave mínima, o que permite acceder ao mínimo en . Este punteiro hai que actualizalo nas demais operacións, o que engade só un custo constante.
Fusión A fusión concatena as listas de raíces de dous montículos e fixa o mínimo no menor dos dous. Pódese facer en tempo constante, e o potencial non cambia, polo que o tempo amortizado é constante.
Inserción A inserción pódese considerar un caso particular da fusión cun só nó. O nó engádese á lista de raíces, aumentando o potencial nunha unidade. O custo amortizado segue sendo constante.
Borrado do mínimo miniatura|alt=Primeira fase do borrado do mínimo.|Figura 2. Primeira fase do borrado do mínimo. miniatura|163x163px|alt=Terceira fase do borrado do mínimo.|Figura 3. Terceira fase do borrado do mínimo. A operación de borrado do mínimo fai a maior parte do traballo de restauración da estrutura. Ten tres fases: Retírase a raíz que contén o mínimo e cada un dos seus fillos convértese en nova raíz sen marcar. Procesar esas novas raíces leva tempo . O número de raíces aumenta en , pero o aumento do potencial é como máximo , xa que retirar marcas tamén o reduce. O custo amortizado desta fase é, polo tanto, para . Pode haber ata raíces. Redúcese o número de raíces enlazando sucesivamente raíces do mesmo grao. Cando dúas raíces teñen o mesmo grao, a de maior chave faise filla da outra, conservando a propiedade do montículo mínimo. O grao da raíz menor aumenta nunha unidade. Isto repítese ata que todas as raíces teñan grao distinto. Para atopar eficientemente árbores do mesmo grao, úsase un vector de lonxitude onde se garda un punteiro a unha raíz de cada grao. Cando se atopa unha segunda raíz do mesmo grao, enlázanse e actualízase o vector. O tempo real é , onde é o número de raíces ao comezo da segunda fase. Ao final hai como máximo raíces, polo que a diferenza de potencial é . Así, o tempo amortizado é , que se simplifica a escollendo abondo grande para que os termos en se cancelen. Búscase na lista final de raíces o mínimo e actualízase o punteiro. Isto leva , porque o número de raíces reduciuse. En conxunto, o tempo amortizado da operación é , sempre que . A demostración dáse na sección seguinte.
Diminución de chave 246x246px|miniatura|alt=Montículo tras diminuír a chave dun nó.|Figura 4. Montículo de Fibonacci da figura 1 tras diminuír a chave do nó 9 a 0. Se diminuír a chave dun nó fai que quede menor ca o seu pai, córtase do pai e convértese nunha nova raíz sen marcar. Se ademais é menor ca a chave mínima, actualízase o punteiro ao mínimo.
A continuación iníciase unha serie de cortes en fervenza, comezando polo pai de . Mentres o nó actual estea marcado, córtase do seu pai e convértese en raíz sen marcar, e prosegue co pai orixinal. O proceso detense ao chegar a un nó sen marcar; se non é raíz, márcase. Se se introducen novas árbores, elimínanse polo menos marcas e engádese como máximo unha. Así, . O custo real é , e o amortizado queda acoutado por unha constante ao escoller adecuadamente o factor do potencial. Unha soa operación pode efectuar cortes: a cota logarítmica do grao non é unha cota logarítmica da altura.
Demostración dos límites de grao O rendemento amortizado dun montículo de Fibonacci depende de que o grao de calquera raíz sexa , onde é o tamaño do montículo. Aquí demóstrase que o tamaño da (sub)árbore con raíz en calquera nó de grao é polo menos , onde é o -ésimo número de Fibonacci. O límite de grao dedúcese diso e do feito (facilmente demostrable por indución) de que para todo , onde é o número áureo. Tense entón , e tomando logaritmos na base , .
Sexa un nó arbitrario, non necesariamente a raíz. Defínese como o tamaño da árbore con raíz en (o número de descendentes, incluído ). Demóstrase por indución sobre a altura de que , onde é o grao de .
Caso base se ten altura 0, entón e .
Caso indutivo supoñamos que ten altura positiva e grao . Sexan os fillos de , ordenados polo momento en que se converteron en fillos de ( o máis antigo e o máis recente), e os seus graos respectivos. Afírmase que para cada : xusto antes de que se convertese en fillo de , xa eran fillos de , polo que tiña grao polo menos . Como as árbores só se combinan cando os graos das súas raíces son iguais, tamén tiña grao polo menos nese momento. Desde entón só puido perder como máximo un fillo (polo proceso de marcaxe), así que o seu grao actual é polo menos . Como as alturas dos son estritamente menores cá de , pódese aplicar a hipótese de indución: Os nós e contribúen polo menos 1 a , e tense
onde o último paso é unha identidade dos números de Fibonacci.
Rendemento Aínda que os montículos de Fibonacci parecen moi eficientes, teñen dous inconvenientes: Son complicados de implementar. Non son tan eficientes na práctica como outras formas de montículo teoricamente menos eficientes. Na súa versión máis simple requiren manipular catro punteiros por nó, mentres que outras estruturas, como o montículo binomial ou o montículo de emparellamento, só necesitan dous ou tres, o que se traduce nun consumo de memoria alto por nó e en factores constantes elevados.
Aínda que o tempo total dunha secuencia de operacións partindo dunha estrutura baleira está acoutado polos límites anteriores, algunhas operacións (moi poucas) poden tardar moito, en particular o borrado do mínimo, que ten tempo linear no peor caso. Por iso os montículos de Fibonacci e outras estruturas amortizadas poden non ser axeitados para sistemas de tempo real.
É posible crear unha estrutura co mesmo rendemento no peor caso que o amortizado do montículo de Fibonacci. Unha delas, a cola de Brodal, é, en palabras do seu creador, «bastante complicada» e «non aplicable na práctica». Inventado en 2012, o montículo de Fibonacci estrito é unha estrutura máis simple (comparada coa de Brodal) coas mesmas cotas no peor caso, aínda que os experimentos mostran que na práctica é máis lento cá cola de Brodal e ca o montículo de Fibonacci básico.
Notas
Véxase tamén Outros artigos Montículo Montículo binario Montículo binomial Cola de prioridade Algoritmo de Dijkstra Algoritmo de Prim Cola de Brodal
Ligazóns externas Simulación en Java dun montículo de Fibonacci Implementación do montículo de Fibonacci en MATLAB Implementación en Ruby do montículo de Fibonacci (con probas) Pseudocódigo do algoritmo do montículo de Fibonacci
Categoría:Algoritmos Categoría:Programación