Pregunta
Implementa un Fibonacci Heap que soporte insert, meld, find-min, extract-min, decrease-key y delete. Explica cómo funcionan conjuntamente las listas de raíces, los enlaces padre-hijo, el grado, los bits de marca y los cortes en cascada, y utiliza una función de potencial para demostrar por qué insert, meld, find-min y decrease-key son O(1) amortizado mientras que extract-min es O(log n) amortizado.
Qué evalúa el entrevistador
- Si distingues el costo real del costo amortizado en lugar de afirmar que toda operación O(1) amortizada siempre toma O(1).
- Si mantienes adecuadamente las listas doblemente enlazadas circulares, el puntero a la raíz mínima, los handles de nodos y los punteros al padre.
- Si decrease-key ejecuta correctamente los cortes, el marcado y los cortes en cascada.
- Si puedes explicar la ventaja teórica, las constantes de ingeniería y las compensaciones frente a los pairing heaps y heaps binarios.
Respuesta modelo
Un Fibonacci Heap es una colección de árboles con orden de heap. Las raíces forman una lista circular doblemente enlazada, y cada nodo almacena un padre, una lista de hijos, el grado y un bit de marca. La estructura retrasa la consolidación hasta extract-min, cuando las raíces se enlazan por grado.
insert agrega un nodo a la lista de raíces y actualiza el mínimo; meld empalma dos listas de raíces. Si decrease-key viola el orden de heap, corta el nodo de su padre y lo agrega a la lista de raíces. Si el padre ya ha perdido un hijo, realiza recursivamente un corte en cascada. Una marca registra si un nodo ya ha perdido un hijo y limita el daño en cascada.
extract-min promueve los hijos de la raíz mínima a la lista de raíces, elimina dicha raíz y enlaza repetidamente raíces con igual grado. Un potencial común es el número de raíces más el doble del número de nodos marcados. Insert y meld incrementan las raíces pero solo pagan una constante; los cortes en cascada reducen los nodos marcados y son pagados por el potencial. El número de enlaces en extract-min está acotado por O(log n) porque el orden de heap limita el grado máximo.
Bosquejo de implementación
El pseudocódigo muestra la ruta crítica de decrease-key; quien llama es dueño del handle del nodo.
decreaseKey(x, newKey):
if newKey > x.key: error
x.key = newKey
p = x.parent
if p is not empty and x.key < p.key:
cut(x, p)
cascadingCut(p)
if x.key < min.key:
min = x
cut(x, p):
removeFromChildList(p, x)
p.degree -= 1
addToRootList(x)
x.parent = empty
x.mark = false
cascadingCut(y):
p = y.parent
if p is empty: return
if y.mark is false:
y.mark = true
else:
cut(y, p)
cascadingCut(p)Durante extract-min, guarda de manera segura el puntero next mientras promueves los hijos antes de eliminar la raíz mínima. El enlazado de raíces de igual grado debe actualizar padre, hijo, grado y marca, seguido de un escaneo para encontrar el nuevo mínimo.
Errores comunes
- Escribir un heap binario basado en arreglos y afirmar que tiene un decrease-key O(1) amortizado como el de un Fibonacci Heap.
- Olvidar limpiar el puntero al padre o la marca después de un corte, corrompiendo la siguiente cascada.
- Eliminar de una lista circular doblemente enlazada mientras se utiliza un puntero next inválido.
- Comparar únicamente las raíces antiguas después de extract-min y olvidar los hijos promovidos en la lista de raíces y en el escaneo del mínimo.
- Comparar solo las cotas asintóticas ignorando la persecución de punteros, la localidad de caché, la asignación de memoria y la complejidad de implementación.
Compensaciones de complejidad
Cuando decrease-key es frecuente, se necesita meld y el análisis amortizado es aceptable, el Fibonacci Heap ofrece una cota teórica atractiva; los ejemplos clásicos son las cotas mejoradas para los algoritmos de Prim y Dijkstra. En producción, los pairing heaps, rank-pairing heaps o heaps binarios a menudo compiten mejor porque son más simples y más amigables con la caché.
Las cotas asumen handles de nodos. Si quienes llaman solo pueden buscar nodos por clave, un índice auxiliar cambia el diseño. Una implementación concurrente también debe definir la propiedad de las listas de raíces y de los handles; la seguridad lock-free no se deduce del análisis amortizado.
Prueba un elemento único, claves duplicadas, meld con un heap vacío, decrease-key repetido y la eliminación del último nodo. Genera secuencias de operaciones aleatorias y compara los valores mínimos y el orden de extract-min con una cola de prioridad de referencia. Construye un nodo que pierda dos hijos consecutivamente para verificar que la primera pérdida lo marque y la segunda pérdida lo corte.
Referencias
- Clase sobre Fibonacci heaps de MIT OpenCourseWare: análisis de potencial y cotas de decrease-key/extract-min.
- Fibonacci Heaps Revisited: un reanálisis de los cortes en cascada y cotas amortizadas.
- Artículo original de Fredman y Tarjan: Fibonacci heaps y su uso en algoritmos de optimización de redes.
Preguntas de seguimiento
¿Por qué los nodos marcados contribuyen con dos unidades al potencial?
Un corte en cascada elimina un nodo marcado y agrega una raíz. Dos unidades de potencial pagan por limpiar la marca y agregar la raíz, manteniendo constante el costo amortizado de toda la cascada.
¿Por qué extract-min es O(log n) amortizado?
Después de eliminar el mínimo y promover a sus hijos, la consolidación mantiene como máximo una raíz por grado. El orden de heap vincula el grado de un nodo con el tamaño de su subárbol, por lo que el grado máximo es O(log n), lo que acota el número de enlaces.
¿Por qué meld puede ser O(1) amortizado?
Dos listas circulares de raíces pueden empalmarse directamente y sus punteros mínimos compararse. Los árboles de igual grado no se consolidan hasta un extract-min posterior.
¿Cuándo es un heap binario una mejor opción?
Usa un heap binario cuando decrease-key sea poco frecuente, la localidad del arreglo importe, los handles de nodos sean inconvenientes o el equipo valore una implementación más simple. Proporciona operaciones O(log n) con un comportamiento de memoria predecible.
¿Cómo se implementa delete?
Reduce la clave del nodo a infinito negativo y llama a extract-min. Una implementación de producción debe definir el dominio de las claves, el comportamiento del centinela y la invalidación de handles para que una clave de negocio válida nunca se confunda con el centinela.