Montón de fibonacci
El montón de Fibonacci ( eng. Fibonacci heap ) es una estructura de datos que es un conjunto de árboles ordenados de acuerdo con la propiedad de una pirámide no decreciente. Michael Fredman y Robert Tarjan introdujeron los montones de Fibonacci en 1984 .
La estructura es una implementación del tipo de datos abstracto " Priority Queue " , y es notable porque las operaciones que no requieren eliminación tienen un tiempo de ejecución amortizado de (para un montón binario y un montón binomial , el tiempo de ejecución amortizado es ). Además de las operaciones estándar , , , el montón de Fibonacci le permite realizar la operación de fusionar dos montones a la vez. INSERTMINDECREASE-KEYUNION
Estructura
- El montón de Fibonacci es una colección de árboles .
- Cada árbol en está sujeto a la propiedad del montón ( ing. min-heap property ): la clave de cada nodo no es menor que la clave de su nodo padre.
- Cada nodo contiene los siguientes punteros y campos
:
- - el campo en el que se almacena la clave;
- — puntero al nodo principal;
- — un puntero a uno de los nodos secundarios;
- - puntero al nodo hermano izquierdo;
- - puntero al nodo hermano derecho;
- - un campo que almacena el número de nodos secundarios;
- — un valor booleano que indica si el nodo ha perdido algún nodo secundario desde que se convirtió en un nodo secundario de algún otro nodo.
- Los nodos secundarios se combinan con la ayuda de punteros y en una lista cíclica doblemente enlazada de nodos secundarios ( ing. child list ) .
- Las raíces de todos los árboles están conectadas por medio de punteros y en una lista cíclica de raíces doblemente enlazada ( eng. root list ).
- Para todo el montón de Fibonacci, también se almacena un puntero al nodo con la clave mínima , que es la raíz de uno de los árboles. Este nodo se llama nodo mínimo .
- El número actual de nodos en se almacena en .
![{\ clave de estilo de visualización [x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/97b36173e5d88ef517878d66a8682fab5bdbabbd)
![{\ estilo de visualización p [x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1b81272b44de4208e118d4381df4c6828cb52da8)
![{\displaystyle hijo[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7983ae8a15176fca40c69829753ebff7acd09cd)
![{\ estilo de visualización a la izquierda [x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0fa7823fa23979d95eb14ab7667a573c22e01b7a)
![{\ estilo de visualización a la derecha [x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/11d488d953d9ad638c15d2594ab597b5e653f15e)
![{\displaystyle grado[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fbb4e65cbfec576877633e2ad6ceaaaae241696)
![{\displaystyle marca[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/542b7e5368647a254202d3b202a71c2df4bf1954)
![{\displaystyle min[H]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a9c75b5f06b71957bc80e0c4e56425cdf8f30b07)
![{\ estilo de visualización n [H]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/92ed2faefa5bfbe5a8314ec6f2b3b1ca9bc406c7)
Operaciones
Creando un nuevo montón de Fibonacci
El procedimiento Make_Fib_Heap devuelve un objeto de montón de fibonacci y = NULL. No hay árboles .
![{\ estilo de visualización n [H] = 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6755b0e87ac6248f20059f3300df0f6cb90f896)
El costo amortizado de un procedimiento es igual a su costo real .
Insertando un Nodo
Fib_Heap_Insert 1 ← 0 2 ← NULO 3 ← NULO 4 ← 5 ← 6 ← FALSO 7 Adjuntar una lista de raíces que contiene , a una lista de raíces 8 si = NULL o 9 entonces ← 10 ← + 1
![{\displaystyle clave[x]<clave[min[H]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/678e72a132e9ae0bbee03a96ad87372a80588594)
El costo amortizado de un procedimiento es igual a su costo real .
Encontrar el nodo mínimo
El procedimiento Fib_Heap_Minimum devuelve un archivo .
El costo amortizado de un procedimiento es igual a su costo real .
Unión de dos montones de Fibonacci
Fib_Heap_Union 1 ← Hacer_Fib_Heap() 2 ← 3 Agregar una lista de raíces a una lista de raíces 4 si ( = NULL) o ( ≠ NULL y < ) 5 luego ← 6 ← 7 Suelta objetos y 8 regresa
![{\displaystyle min[H_{1}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c06be73dfdc2ebd7713d3a946a91127d751c86dd)
![{\displaystyle min[H_{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7e4c15d462e9bc769e328ba3b93711b75d21de68)
![{\ clave de estilo de visualización [min [H_ {2}]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd38f11d72e5ef38a1dba12f4131e25d75e72ccf)
![{\ clave de estilo de visualización [min [H_ {1}]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05f66202f4a1f1ef6be319ab0caa46a70aa702da)
![{\displaystyle n[H_{1}]+n[H_{2}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e121253884bf636242ef97daaf19c6dffa47226e)
El costo amortizado de un procedimiento es igual a su costo real .
Extrayendo el nodo mínimo
Fib_Heap_Extract_Min 1 ← 2 si ≠ NULL 3 luego para cada hijo del nodo 4 haga Add to root list 5 ← NULL 6 Eliminar de la lista raíz 7 si = 8 entonces ← NULL 9 más ← 10 Consolidar 11 ← 12 volver
![{\ estilo de visualización a la derecha [z]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef6c0ca5e045f05b51a8e85a71a2652179a28f23)
![{\ estilo de visualización n [H] -1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ed2c368ce89423e341bd76679b6a7a18e720e17)
En una de las etapas de la operación de extracción del nodo mínimo, se realiza la compactación ( ing. consolidación ) de la lista de raíces . Para ello, utilice el procedimiento de ayuda de Consolidar. Este procedimiento utiliza una matriz auxiliar . Si , entonces actualmente es una raíz con grado .
Consolidar 1 para ← 0 a 2 hacer ← NULL 3 for para cada nodo en la lista raíz 4 do ← 5 ← 6 while ≠ NULL 7 do ← //Nodo con el mismo grado que 8 si 9 luego intercambia ↔ 10 Fib_Heap_Link 11 ← NULL 12 ← 13 ← 14 ← NULO 15 para ← 0 a 16 hacer si ≠ NULL 17 luego agregar a la lista raíz 18 si = NULL o 19 luego ← Fib_Heap_Link 1 Eliminar de la lista raíz 2 Crear nodo secundario , incrementar 3 ← FALSO![{\displaystyle A[0..D[n[H]]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/16a8aaf0c3fea41669e247dae3c99739997608c7)
![{\ estilo de visualización A [i] = y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1773ac5c49b3da8c9e09a416b77c6fe80c7a307)
![{\displaystyle grado[y]=i}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dd44fdeab4b5b858a4e9e6d2c45ffcdcf96af6fc)
![{\ estilo de visualización D (n [H])}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6561060baee3b079d50a46f93444ab97506a9f5)
![{\ estilo de visualización A [i]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a0d7a8a3371fad84f7032042e8d1e1caf6aa15e)
![{\ estilo de visualización A [d]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/042feac7bdbe07a6252a95c7129cd511404b28ff)
![{\displaystyle tecla[x]>tecla[y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/07c4916c2e2b340131b0a221ca3590ecf2f98357)
![{\displaystyle clave[A[i]]<tecla[min[H]]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a3a421f33d981dab3125f64324a79d34de6ae8f4)
![{\displaystyle marca[y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aecc871ae5dc12bfc3206f13c2a545fcd974bae4)
El costo amortizado de extraer el nudo mínimo es .
Tecla decreciente
Fib_Heap_Decrease_Key 1 si 2 entonces error "La nueva clave es mayor que la actual" 3 ← 4 ← 5 si ≠ NULL y 6 luego Cortar 7 Cascading_Cut 8 si 9 entonces ← Cortar 1 Eliminar de la lista de nodos secundarios , reducir 2 Agregar a la lista de raíces 3 ← NULL 4 ← FALSO Cascading_Cut 1 ← 2 si ≠ NULL 3 entonces si = FALSO 4 entonces ← VERDADERO 5 más Cortar 6 Cascading_Cut
![{\displaystyle k>clave[x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce139201a27c8a99d5bc6e6b21ccff58421d5225)
![{\displaystyle clave[x]<clave[y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b19c276ef004ee01d9243b7dae5ca4d3550d9b6)
![{\displaystyle grado[y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a84c755349b58d4dbdf25eee53cabead167a765c)
![{\ estilo de visualización p [y]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8c4860ad95bb383f9e80c71fb26ef7e3c706f92)
El costo amortizado de la reducción clave no excede .
Eliminar un nodo
Fib_Heap_Delete 1 Fib_Heap_Decrease_Key ∞ 2 Fib_Heap_Extract_Min
El tiempo de ejecución amortizado del procedimiento es de .
Véase también
Enlaces
- Implementación de estructura en C
- Vladimir Alekseev, Vladimir Talanov, Conferencia 7: Montones binomiales y de Fibonacci // "Estructuras de datos y modelos computacionales", 26.09.2006, intuit.ru
Literatura
- Thomas H. Kormen et al.Algoritmos : construcción y análisis. - 2ª ed. - M. : Williams Publishing House , 2007. - S. 1296. - ISBN 5-8459-0857-4 .
- Mehlhorn, Kurt, Sanders, Peter. 6.2.2 Montones de Fibonacci // Algoritmos y estructuras de datos: la caja de herramientas básica. - Springer, 2008. - 300 págs. — ISBN 978-3-540-77978-0 .