data structures - ¿Cuál es la intuición detrás de la estructura de datos del montón de Fibonacci?

data-structures fibonacci-heap (1)

He leído el artículo de Wikipedia sobre montones de Fibonacci y he leído la descripción de CLRS de la estructura de datos, pero proporcionan poca intuición sobre por qué funciona esta estructura de datos. ¿Por qué los montones de Fibonacci se diseñan tal como son? ¿Cómo trabajan?

¡Gracias!

Esta respuesta va a ser bastante larga, pero espero que ayude a proporcionar una idea de dónde viene el montón de Fibonacci. Voy a suponer que ya está familiarizado con los montones binomiales y el análisis amortizado .

Motivación: ¿Por qué montones de Fibonacci?

Antes de saltar a montones de Fibonacci, probablemente sea bueno explorar por qué los necesitamos en primer lugar. Hay muchos otros tipos de montones (montones binarios y montones binomiales , por ejemplo), entonces ¿por qué necesitamos otro?

La razón principal aparece en el algoritmo de Dijkstra y el algoritmo de Prim . Ambos algoritmos de gráficos funcionan manteniendo un nodo de retención de colas de prioridad con prioridades asociadas. Curiosamente, estos algoritmos se basan en una operación de almacenamiento dinámico denominada clave de disminución que toma una entrada que ya está en la cola de prioridad y luego disminuye su clave (es decir, aumenta su prioridad). De hecho, gran parte del tiempo de ejecución de estos algoritmos se explica por la cantidad de veces que tiene que llamar a la tecla disminuir. Si pudiéramos construir una estructura de datos que optimizara la tecla de disminución, podríamos optimizar el rendimiento de estos algoritmos. En el caso del montón binario y el binomial, la tecla disminuir toma tiempo O (log n), donde n es el número de nodos en la cola de prioridad. Si pudiéramos dejar eso en O (1), entonces las complejidades de tiempo del algoritmo de Dijkstra y el algoritmo de Prim caerían de O (m log n) a (m + n log n), que es asintóticamente más rápido que antes. Por lo tanto, tiene sentido intentar construir una estructura de datos que admita disminuir-clave de manera eficiente.

Hay otra razón para considerar diseñar una mejor estructura de pila. Al agregar elementos a un montón binario vacío, cada inserción toma tiempo O (log n). Es posible construir un montón binario en el tiempo O (n) si conocemos todos los n elementos de antemano, pero si los elementos llegan a una secuencia esto no es posible. En el caso del montón binomial, la inserción de n elementos consecutivos toma el tiempo amortizado O (1) cada uno, pero si las inserciones están entrelazadas con eliminaciones, las inserciones pueden terminar tomando Ω (log n) cada vez. Por lo tanto, es posible que deseemos buscar una implementación de cola de prioridad que optimice las inserciones para tomar el tiempo O (1) cada una.

Primer paso: Lazy Binomial Heaps

Para comenzar a construir el montón de Fibonacci, vamos a comenzar con un montón binomial y modificarlo para intentar hacer que las inserciones lleven tiempo O (1). No es demasiado irrazonable probar esto; después de todo, si vamos a hacer muchas inserciones y no tantas eliminaciones, tiene sentido optimizar las inserciones.

Si recuerda, el binomio funciona al almacenar todos los elementos en el montón en una colección de árboles binomiales . Un árbol binomial de orden n tiene 2 ⁿ nodos, y el montón es estructuras como una colección de árboles binomiales que obedecen a la propiedad de montón. Normalmente, el algoritmo de inserción en un montón binomial funciona de la siguiente manera:

Cree un nuevo nodo singleton (este es un árbol de orden 0).
Si hay un árbol de orden 0:
- Combina los dos árboles del orden 0 en un árbol de orden 1.
- Si hay un árbol de orden 1:
  - Combina los dos árboles de la orden 1 en una orden de árbol 2.
  - Si hay un árbol de orden 2:
  - ...

Este proceso asegura que en cada momento, haya como máximo un árbol de cada orden. Como cada árbol contiene exponencialmente más nodos que su orden, esto garantiza que el número total de árboles sea pequeño, lo que permite que las dequeues se ejecuten rápidamente (porque no tenemos que mirar demasiados árboles diferentes después de hacer un paso de dequeue-min).

Sin embargo, esto también significa que el peor tiempo de ejecución para insertar un nodo en un montón binomial es Θ (log n), porque podríamos tener Θ (log n) árboles que necesitan fusionarse. Esos árboles necesitan fusionarse solo porque necesitamos mantener el número de árboles bajo al hacer un paso de dequeue, y no hay absolutamente ningún beneficio en futuras inserciones para mantener baja la cantidad de árboles.

Esto introduce la primera salida de los montones binomiales:

Modificación 1 : cuando inserte un nodo en el montón, simplemente cree un árbol de orden 0 y agréguelo a la colección de árboles existente. No consolide los árboles juntos.

Hay otro cambio que podemos hacer. Normalmente, cuando fusionamos dos montones binomiales, hacemos un paso de combinación para combinarlos de una manera que asegure que haya como máximo un árbol de cada orden en el árbol resultante. Nuevamente, hacemos esta compresión para que las dequeues sean rápidas, y no hay una razón real por la cual la operación de fusión deba pagar por esto. Por lo tanto, haremos un segundo cambio:

Modificación 2 : Al unir dos montones, simplemente combine todos los árboles sin hacer ninguna fusión. No consolide ningún árbol juntos.

Si hacemos este cambio, obtenemos fácilmente O (1) rendimiento en nuestras operaciones en cola, ya que lo único que estamos haciendo es crear un nuevo nodo y agregarlo a la colección de árboles. Sin embargo, si hacemos este cambio y no hacemos nada más, rompemos completamente el rendimiento de la operación de dequeue-min. Recuerde que dequeue-min necesita escanear a través de las raíces de todos los árboles en el montón después de eliminar el valor mínimo para que pueda encontrar el valor más pequeño. Si agregamos Θ (n) nodos insertándolos en el camino, nuestra operación de dequeue tendrá que pasar Θ (n) tiempo revisando todos estos árboles. Es un gran golpe de rendimiento ... ¿podemos evitarlo?

Si nuestras inserciones realmente solo agregan más árboles, entonces la primera dequeue que hagamos ciertamente tomará Ω (n) tiempo. Sin embargo, eso no significa que cada dequeue tiene que ser costoso. ¿Qué sucede si, después de hacer un dequeue, unimos todos los árboles en el montón juntos de manera que terminemos con solo un árbol de cada orden? Esto llevará un largo tiempo inicialmente, pero si comenzamos a hacer múltiples dequeues en sucesión, esas dequeues futuras serán significativamente más rápidas debido a que hay menos árboles por ahí.

Sin embargo, hay un pequeño problema con esta configuración. En un montón binomial normal, los árboles siempre se almacenan en orden. Si seguimos arrojando árboles nuevos a nuestra colección de árboles, uniéndolos en momentos aleatorios y agregando incluso más árboles después de eso, no hay garantía de que los árboles estén en cualquier orden. Por lo tanto, vamos a necesitar un nuevo algoritmo para unir esos árboles.

La intuición detrás de este algoritmo es la siguiente. Supongamos que creamos una tabla hash que mapea desde órdenes de árbol a árboles. Luego podríamos hacer la siguiente operación para cada árbol en la estructura de datos:

Mire hacia arriba y vea si ya hay un árbol de ese orden.
Si no, inserte el árbol actual en la tabla hash.
De otra manera:
- Combina el árbol actual con el árbol de ese orden, eliminando el árbol viejo de la tabla hash.
- Repite recursivamente este proceso.

Esta operación asegura que, cuando terminemos, haya como máximo un árbol de cada orden. También es relativamente eficiente. Supongamos que comenzamos con T árboles totales y terminamos con t árboles totales. El número de fusiones totales que terminaremos haciendo será T - t - 1, y cada vez que realicemos una fusión, llevará tiempo O (1) hacerlo. Por lo tanto, el tiempo de ejecución para esta operación será lineal en la cantidad de árboles (cada árbol se visita al menos una vez) más el número de fusiones realizadas.

Si la cantidad de árboles es pequeña (digamos, Θ (log n)), esta operación solo tomará tiempo O (log n). Si la cantidad de árboles es grande (digamos, Θ (n)), esta operación tomará Θ (n) tiempo, pero solo dejará Θ (log n) árboles restantes, haciendo que las dequeues futuras sean mucho más rápidas.

Podemos cuantificar cuánto mejor obtendrán las cosas haciendo un análisis amortizado y utilizando una función potencial. Deje Φ ser nuestra función potencial y seamos the la cantidad de árboles en la estructura de datos. Esto significa que los costos de las operaciones son los siguientes:

Insertar : Funciona O (1) y aumenta el potencial en uno. El costo amortizado es O (1).
Fusionar : O (1) funciona. El potencial de un montón se reduce a 0 y el potencial del otro montón se incrementa en una cantidad correspondiente, por lo que no hay un cambio neto en el potencial. El costo amortizado es, por lo tanto, O (1).
Dequeue-Min : funciona O (#trees + #merges) y reduce el potencial a Θ (log n), la cantidad de árboles que tendríamos en el árbol binomial si estuviéramos fusionando los árboles con entusiasmo. Podemos dar cuenta de esto de una manera diferente. Hagamos que la cantidad de árboles se escriba como Θ (log n) + E, donde E es el número "en exceso" de árboles. En ese caso, el trabajo total realizado es Θ (log n + E + #merges). Tenga en cuenta que haremos una combinación por árbol excedente, por lo que el trabajo total realizado es Θ (log n + E). Como nuestro potencial disminuye el número de árboles desde Θ (log n) + E a Θ (log n), la caída en el potencial es -E. Por lo tanto, el costo amortizado de un dequeue-min es Θ (log n).

Otra forma intuitiva de ver por qué el costo amortizado de un dequeue-min es Θ (log n) es observando por qué tenemos árboles excedentes. ¡Estos árboles adicionales están ahí porque esos insertos codiciosos zurcidos están haciendo todos estos árboles extra y no están pagando por ellos! Por lo tanto, podemos "recargar" el costo asociado con hacer todas las fusiones a las inserciones individuales que tomaron todo ese tiempo, dejando atrás la operación de "núcleo" log (log n) y un montón de otras operaciones de las cuales nos culparemos las inserciones

Por lo tanto:

Modificación 3 : en una operación de dequeue-min, consolide todos los árboles para asegurarse de que haya como máximo un árbol de cada orden.

En este punto, tenemos inserción y fusión ejecutándose en el tiempo O (1) y dequeues corriendo en tiempo amortizado O (log n). ¡Eso es bastante ingenioso! Sin embargo, todavía no tenemos la tecla de disminución funcionando todavía. Esa va a ser la parte más difícil.

Paso dos: implementación de la clave de disminución

En este momento, tenemos un "montón binomial perezoso" en lugar de un montón de Fibonacci. El cambio real entre un montón binomial y un montón de Fibonacci es cómo implementamos la tecla disminuir.

Recuerde que la operación de disminución de la clave debe tomar una entrada que ya está en el montón (por lo general, tendríamos un puntero) y una nueva prioridad que es menor que la prioridad existente. Luego cambia la prioridad de ese elemento a la nueva prioridad más baja.

Podemos implementar esta operación muy rápidamente (en el tiempo O (log n)) usando un algoritmo directo. Tome el elemento cuya clave debe reducirse (que puede ubicarse en el tiempo O (1); recuerde, estamos asumiendo que tenemos un puntero) y disminuya su prioridad. Luego, cancélelo repetidamente con su nodo padre siempre que su prioridad sea menor que su padre, deteniéndose cuando el nodo se detiene o cuando llega a la raíz del árbol. Esta operación lleva tiempo O (log n) porque cada árbol tiene una altura como máximo O (log n) y cada comparación toma tiempo O (1).

Recuerde, sin embargo, que estamos tratando de hacerlo aún mejor que esto, ¡queremos que el tiempo de ejecución sea O (1)! Es un partido muy difícil de igualar. No podemos usar ningún proceso que mueva el nodo hacia arriba o hacia abajo del árbol, ya que esos árboles tienen alturas que pueden ser Ω (log n). Tendremos que intentar algo más drástico.

Supongamos que queremos disminuir la clave de un nodo. La única forma en que se violará la propiedad de montón será si la nueva prioridad del nodo es menor que la de su padre. Si miramos el subárbol enraizado en ese nodo particular, seguirá obedeciendo la propiedad de montón. Entonces, esta es una idea totalmente descabellada: ¿qué pasa si cada vez que disminuimos la clave de un nodo, cortamos el enlace al nodo padre, y luego hacemos que todo el subárbol enraizado en el nodo vuelva al nivel superior del árbol?

Modificación 4 : haga que la tecla disminuir disminuya la clave de un nodo y, si su prioridad es menor que la prioridad de sus padres, córtela y agréguela a la lista raíz.

¿Cuál será el efecto de esta operación? Varias cosas sucederán

El nodo que anteriormente tenía nuestro nodo como un niño ahora piensa que tiene el número incorrecto de hijos. Recuerde que un árbol binomial de orden n se define para tener n hijos, pero eso ya no es cierto.
La colección de árboles en la lista raíz aumentará, lo que aumentará el costo de futuras operaciones de dequeue.
Los árboles en nuestro montón ya no serán necesariamente árboles binomiales. Pueden ser árboles binomiales "anteriormente" que perdieron niños en diversos momentos.

El número (1) no es demasiado problema. Si cortamos un nodo de su elemento primario, podemos simplemente disminuir el orden de ese nodo en uno para indicar que tiene menos hijos de los que creía que tenía anteriormente. El número (2) tampoco es un problema. Podemos simplemente recargar el trabajo adicional realizado en la siguiente operación de dequeue-min a la operación de tecla de disminución.

El número (3) es un problema muy, muy serio que tendremos que abordar. Aquí está el problema: la eficiencia de un montón binomial se deriva parcialmente del hecho de que cualquier colección de n nodos se puede almacenar en una colección de árboles of (log n) de diferente orden. La razón de esto es que cada árbol binomial tiene 2 ⁿ nodos. Si podemos comenzar a cortar los nodos de los árboles, corremos el riesgo de tener árboles que tengan una gran cantidad de niños (es decir, un orden elevado) pero que no tengan muchos nodos. Por ejemplo, supongamos que comenzamos con un solo árbol de orden ky luego realizamos operaciones de tecla de disminución en todos los nietos de k. Esto deja k como un árbol con orden k, pero que solo contiene k + 1 nodos totales. Si seguimos repitiendo este proceso en todas partes, podríamos terminar con un grupo de árboles de varios órdenes que tienen un número muy pequeño de niños. En consecuencia, cuando hacemos nuestra operación de fusión para agrupar los árboles, es posible que no reduzcamos la cantidad de árboles a un nivel manejable, rompiendo el límite de tiempo de log (log n) que realmente no queremos perder.

En este punto, estamos en un aprieto. Necesitamos tener mucha flexibilidad con la forma en que se pueden remodelar los árboles para que podamos obtener la funcionalidad O (1) de disminución de tiempo, pero no podemos dejar que los árboles se modifiquen arbitrariamente o terminaremos con disminución. el tiempo de ejecución amortizado de la clave aumenta a algo mayor que O (log n).

La idea necesaria -y, sinceramente, lo que creo que es el verdadero genio en el montón de Fibonacci- es un compromiso entre los dos. La idea es la siguiente. Si cortamos un árbol de su padre, ya estamos planeando disminuir el rango del nodo padre en uno. El problema realmente surge cuando un nodo pierde muchos niños, en cuyo caso su rango disminuye significativamente sin que haya ningún nodo más arriba en el árbol que lo sepa. Por lo tanto, diremos que cada nodo solo puede perder un hijo. Si un nodo pierde un segundo hijo, cortamos ese nodo de su padre, lo que propaga la información de que los nodos faltan más arriba en el árbol.

Resulta que este es un gran compromiso. Nos permite hacer teclas de disminución rápidamente en la mayoría de los contextos (siempre que los nodos no sean hijos del mismo árbol), y solo rara vez tenemos que "propagar" una tecla de disminución cortando un nodo de su padre y luego cortando ese nodo de sus abuelos.

Para realizar un seguimiento de qué nodos han perdido hijos, asignaremos un bit de "marca" a cada nodo. Cada nodo tendrá inicialmente el bit de marca borrado, pero cada vez que pierde un niño tendrá el bit establecido. Si pierde un segundo hijo después de que el bit ya se haya configurado, borraremos el bit, luego cortaremos el nodo de su padre.

Modificación 5 : Asigne un bit de marca a cada nodo que sea inicialmente falso. Cuando un niño es cortado de un padre sin marcar, marque el padre. Cuando un niño es cortado de un padre marcado, desmarque el padre y corte al padre de su padre.

En esta vieja pregunta de Desbordamiento de pila , esbocé una prueba que muestra que si se permite que los árboles se modifiquen de esta manera, entonces cualquier árbol de orden n debe contener al menos Θ (φ ⁿ ) nodos, donde φ es el dorado relación , alrededor de 1.61. Esto significa que la cantidad de nodos en cada árbol sigue siendo exponencial en el orden del árbol, aunque es un exponente inferior al anterior. Como resultado, el análisis que hicimos anteriormente sobre el tiempo de complejidad de la operación de tecla de disminución aún se mantiene, aunque el término oculto en el bit Θ (log n) será diferente.

Hay una última cosa a considerar: ¿qué pasa con la complejidad de la tecla de disminución? Anteriormente, era O (1) porque cortamos el árbol enraizado en el nodo apropiado y lo movimos a la lista raíz. Sin embargo, ahora podríamos tener que hacer un "corte en cascada", en el cual cortamos un nodo de su padre, luego cortamos ese nodo de su padre, etc. ¿Cómo le da a O (1) teclas de disminución de tiempo?

La observación aquí es que podemos agregar un "cargo" a cada operación de disminución de la clave que luego podemos gastar para cortar el nodo padre de su padre. Como solo cortamos un nodo de su elemento primario si ya ha perdido dos elementos secundarios, podemos pretender que cada operación de tecla de reducción paga el trabajo necesario para cortar su nodo primario. Cuando cortamos el elemento primario, podemos cargar el costo de hacerlo nuevamente a una de las operaciones anteriores de tecla de disminución. En consecuencia, aunque cualquier operación de tecla decreciente individual puede tardar mucho tiempo en finalizar, siempre podemos amortizar el trabajo en las llamadas anteriores para que el tiempo de ejecución se amortice O (1).

Paso tres: ¡Listas vinculadas abultadas!

Hay un último detalle del que tenemos que hablar. La estructura de datos que he descrito hasta ahora es engañosa, pero no parece catastróficamente complicada. Los montones de Fibonacci tienen una reputación de ser temibles ... ¿por qué es eso?

La razón es que para implementar todas las operaciones descritas anteriormente, las estructuras de árbol deben implementarse de manera muy inteligente.

Normalmente, representaría un árbol multivía ya sea haciendo que cada padre señale hacia abajo a todos los niños (quizás al tener una matriz de niños) o utilizando la representación izquierda-niño / derecho-hermano , donde el padre tiene un puntero a uno niño, que a su vez apunta a una lista de los otros niños. Para un montón binomial, esto es perfecto. La operación principal que tenemos que hacer en los árboles es una operación de combinación en la que hacemos que un nodo raíz sea hijo de otro, por lo que es perfectamente razonable para los indicadores del árbol dirigidos de padres a hijos.

El problema en un montón de Fibonacci es que esta representación es ineficiente cuando se considera el paso de disminuir la clave. Los montones de Fibonacci necesitan admitir todas las manipulaciones básicas del puntero de un montón de binomios estándar y la capacidad de cortar un único hijo de un padre.

Considere las representaciones estándar de árboles de múltiples vías. Si representamos el árbol haciendo que cada nodo padre almacene una matriz o una lista de punteros a sus elementos secundarios, entonces no podemos eliminar de manera eficiente (en O (1)) un nodo secundario de la lista de elementos secundarios. En otras palabras, el tiempo de ejecución de la tecla de disminución estaría dominado por el paso de contabilidad de eliminar al hijo en lugar del paso lógico de mover un subárbol a la lista raíz. El mismo problema aparece en la representación del niño izquierdo, hermano derecho.

La solución a este problema es almacenar el árbol de una manera extraña. Cada nodo padre almacena un puntero a uno (y arbitrario) único de sus hijos. Los niños se almacenan en una lista de enlaces circulares, y cada uno regresa a su padre. Dado que es posible concatenar dos listas vinculadas circularmente en el tiempo O (1) e insertar o eliminar una sola entrada de una en O (1) tiempo, esto hace posible apoyar eficientemente las operaciones de árbol necesarias:

Haga que un árbol sea hijo de otro: si el primer árbol no tiene hijos, configure su puntero secundario para que apunte al segundo árbol. De lo contrario, empalme el segundo árbol en la lista secundaria circularmente vinculada del primer árbol.
Eliminar un elemento secundario de un árbol: empalme ese nodo secundario de la lista vinculada de elementos secundarios para el nodo primario. Si es el nodo único elegido para representar los elementos secundarios del nodo primario, elija uno de los nodos hermanos para reemplazarlo (o establezca el puntero a nulo si es el último elemento secundario).

Hay muchos casos absurdos para considerar y verificar al realizar todas estas operaciones simplemente debido a la cantidad de casos de bordes diferentes que pueden surgir. La sobrecarga asociada con todos los malabares del puntero es una de las razones por las que los montones de Fibonacci son más lentos de lo que su complejidad asintótica podría sugerir (el otro grande es la lógica para eliminar el valor mínimo, que requiere una estructura de datos auxiliar).

Modificación 6 : Use una representación personalizada del árbol que soporte la unión eficiente de árboles y cortar un árbol de otro árbol.

Conclusión

Espero que esta respuesta arroje algo de luz sobre el misterio que es el montón de Fibonacci. Espero que pueda ver la progresión lógica desde una estructura más simple (el montón binomial) a una estructura más compleja mediante una serie de pasos simples basados en ideas razonables. No es irrazonable querer hacer las inserciones amortizadas de manera eficiente a expensas de las eliminaciones, y tampoco es una locura implementar una clave de reducción cortando los subárboles. A partir de ahí, el resto de los detalles están en garantizar que la estructura sea aún eficiente, pero son más las consecuencias de las otras partes que las causas .

Si está interesado en obtener más información sobre los montones de Fibonacci, le recomendamos que consulte esta serie de diapositivas para conferencias. La primera parte presenta montones binomiales y muestra cómo funcionan los montones de binomios perezosos. La segunda parte explora los montones de Fibonacci. Estas diapositivas entran en una profundidad más matemática que la que he cubierto aquí.

¡Espero que esto ayude!