Entrevista técnica de código: ¿Cómo implementarías un pairing heap con decrease-key?

Planteamiento y contexto

Implementa una cola de prioridad mínima combinable (meldable min-priority queue) para un planificador de eventos cuyas prioridades de tareas pueden disminuir. Un binary heap maneja las operaciones básicas, pero meld y decrease-key añaden costo. Implementa un pairing heap con handles, enlace (linking), fusión en dos pasadas, eliminación y casos límite.

Los pairing heaps se introdujeron en 1986 como montículos autoajustables diseñados para combinar una implementación sencilla con un buen rendimiento práctico; el artículo original solo proporcionó un análisis de complejidad parcial. La entrevista evalúa si distingues entre la corrección del código, el razonamiento amortizado y las afirmaciones de complejidad no probadas.

Qué evalúa el entrevistador

Cubre el invariante de min-heap, el meld en tiempo constante, el emparejamiento de hermanos en dos pasadas, los handles obsoletos (stale handles), el decrease-key mediante corte y reenlace, claves vacías y duplicadas, la propiedad de la memoria y los compromisos frente a binary heaps y Fibonacci heaps.

Preguntas de aclaración para hacer

• ¿Se requiere decrease-key o solo push/pop, y cuál es la mezcla de operaciones?
• ¿Los handles de los nodos deben permanecer estables y cómo se detectan los handles obsoletos?
• ¿Se permite la recursión y cuáles son el tamaño máximo del montículo y los límites de la pila (stack budgets)?
• ¿El comparador puede lanzar excepciones o cambiar, y se admiten prioridades duplicadas?
• ¿El objetivo es la claridad pedagógica, la velocidad práctica con constantes bajas o una demostración estricta de peor caso?

Una respuesta de 30 segundos

“Cada nodo almacena una clave, carga útil (payload), padre, primer hijo y siguiente hermano, con un handle que apunta al nodo. Link compara dos raíces y hace que la raíz con mayor clave sea el primer hijo de la raíz con menor clave. Delete-min desacopla la raíz, enlaza a los hermanos de izquierda a derecha en pares y luego los fusiona de derecha a izquierda. Decrease-key corta un nodo que no es raíz y lo combina como raíz mediante meld. Realiza un seguimiento del estado de los handles y describe la complejidad utilizando análisis amortizados y establecidos.”

Análisis detallado paso a paso

Paso 1: Definir nodos y handles

Almacena clave, payload, padre, primer hijo y hermano derecho en cada nodo. Un handle apunta al nodo y lleva un marcador de actividad o generación, lo que evita decrease-key después de una eliminación. Una raíz no tiene padre y el final de la lista de hermanos es nulo.

Node { key, value, parent, firstChild, nextSibling, alive }
Heap { root, size }

El comparador solo ordena valores y no muta los nodos. Trata las claves iguales como nodos distintos y aplica la política de estabilidad requerida.

Paso 2: Implementar link y meld

link(a, b) compara dos raíces, convierte la raíz de mayor clave en el primer hijo de la raíz de menor clave y actualiza los punteros de padre y hermanos. meld solo enlaza dos raíces; un montículo vacío devuelve la otra raíz.

Después de cada actualización de punteros, verifica mediante aserciones que la raíz no tenga padre, que cada hijo apunte de vuelta a su padre y que el tamaño no haya cambiado. Una compilación de depuración puede recorrer la estructura en busca de ciclos, pero las operaciones en producción no deben realizar una verificación lineal cada vez.

Paso 3: Implementar insert y find-min

insert crea un montículo de un solo elemento (singleton), lo combina con la raíz mediante meld y devuelve un handle estable. find-min lee la raíz; un montículo vacío devuelve el resultado vacío de la API o un error en lugar de desreferenciar un puntero nulo.

Si las funciones invocadoras retienen handles, mover o hacer crecer el montículo no debe invalidarlos. Asigna nodos de forma independiente o utiliza una capa de indirección estable, y documenta si el montículo es propietario de los nodos o solo de los payloads.

Paso 4: Implementar delete-min de dos pasadas

Tras eliminar la raíz, desacopla su lista de hijos para convertirla en una lista de raíces. En la primera pasada, enlaza raíces adyacentes de izquierda a derecha en pares; conserva la última raíz cuando la cantidad sea impar. En la segunda pasada, combina los resultados de derecha a izquierda mediante meld.

deleteMin(h):
  children = detachChildren(h.root)
  pairs = linkAdjacent(children)
  newRoot = mergeRightToLeft(pairs)
  invalidate(h.root)
  h.root = newRoot
  h.size -= 1

Limpia los punteros antiguos de padre y hermano durante la fusión para no retener la raíz eliminada. Utiliza una lista iterativa para una cadena larga de hermanos con el fin de evitar un desbordamiento de pila (stack overflow).

Paso 5: Implementar decrease-key

Rechaza una nueva clave que no sea menor, o define una operación increase-key por separado. Para la raíz, actualiza solo la clave. Para un nodo que no es raíz, córtalo de la lista de hijos de su padre, repara los punteros de hermanos y combínalo como una raíz independiente mediante meld.

Cortar requiere el hermano anterior: recorre la lista del padre o añade un puntero prevSibling y asume el mantenimiento adicional. Devuelve un error ante un handle obsoleto, un nodo de otro montículo o un montículo destruido.

Paso 6: Probar invariantes y complejidad

Utiliza pruebas diferenciales aleatorias contra una cola de prioridad estándar, cubriendo claves duplicadas, montículos vacíos, decrease-key repetidos, eliminación de cada nodo y meld aleatorio. Después de cada operación, verifica que la raíz sea mínima, que el tamaño coincida con los nodos activos y que los enlaces padre-hijo sean acíclicos.

Separa los límites demostrados, la intuición amortizada y las mediciones. insert y meld en pairing heaps tienen constantes pequeñas, pero los análisis estrictos para delete-min y decrease-key no son una licencia para afirmar que cada operación sea O(log n) en el peor caso. Especifica las suposiciones y compara con binary heaps y Fibonacci heaps.

Una respuesta de ejemplo sólida

Utilizaría punteros a padre, primer hijo y siguiente hermano junto con handles estables para link, meld, delete-min de dos pasadas y decrease-key. En un decrease-key sobre un nodo que no es raíz, este se corta de su lista de hermanos antes de combinarse como una nueva raíz mediante meld; delete-min empareja de izquierda a derecha y fusiona de derecha a izquierda. Realizaría pruebas diferenciales contra una cola de prioridad estándar, verificaría los invariantes de aciclicidad y tamaño, y distinguiría entre análisis amortizado, cotas de peor caso y benchmarks prácticos.

Errores comunes

• Modificar solo la clave → el orden del montículo y los enlaces con el padre se rompen → corta y combina mediante meld cada decrease-key que no sea raíz.
• Invertir el orden de las dos pasadas → la forma y los resultados son incorrectos → empareja de izquierda a derecha y luego fusiona de derecha a izquierda.
• Utilizar un handle eliminado → use-after-free o mutación entre montículos distintos → invalida y verifica la pertenencia.
• Afirmar que cada operación es O(log n) en el peor caso → la complejidad carece de sustento → separa el análisis amortizado, el análisis parcial y las mediciones.
• Usar recursión en una lista larga de hermanos → stack overflow → utiliza una lista iterativa.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Por qué no utilizar directamente un binary heap?

Los binary heaps tienen una disposición en arreglo simple y límites estables; los pairing heaps pueden tener constantes más pequeñas con meld y decrease-key frecuentes. Elige según la mezcla de operaciones, la localidad de memoria y los requisitos de demostración.

Pregunta de seguimiento 2: ¿Cómo puede decrease-key evitar recorrer los hermanos?

Añade un puntero prevSibling o un índice de conjunto de hijos, pero manteniendo más punteros en cada link y corte. Compara ese costo de espacio y mantenimiento con el recorrido lineal.

Pregunta de seguimiento 3: ¿Cómo se elimina un handle arbitrario?

Reduce su clave a infinito negativo, llama a decrease-key y luego a delete-min. Asegúrate de que el comparador y el valor centinela sean seguros, e invalida el handle correctamente.

Pregunta de seguimiento 4: ¿Cuándo elegirías un Fibonacci heap?

Considéralo cuando la cota amortizada teórica de decrease-key y la demostración algorítmica importen más que la complejidad de implementación. El código de ingeniería aún requiere mediciones de localidad, memoria y cargas de trabajo reales.