Entrevista de código: ¿Cómo implementarías un montículo fusionable aleatorizado (Randomized Meldable Heap)?

Planteamiento y contexto

Estás implementando una cola de prioridad mínima fusionable para un programador de tareas. Los llamadores combinan frecuentemente dos colas, luego insertan trabajo y eliminan la prioridad más pequeña. Implementa meld, insert, find-min y extract-min, y establece tus elecciones respecto a la aleatorización, montículos vacíos, claves duplicadas y la propiedad de los nodos.

Un montículo fusionable aleatorizado representa el orden de montículo como un árbol binario sin metadatos de rango como el rango izquierdista (leftist rank). En cada fusión, elige aleatoriamente la rama recursiva izquierda o derecha. La entrevista evalúa invariantes, suposiciones de probabilidad y comprobabilidad.

Qué evalúa el entrevistador

Cubre el invariante de raíz mínima, la semántica de intercambio y consumo de meld, los límites de bits aleatorios, claves duplicadas, propiedad, profundidad de recursión, destrucción y la diferencia entre cotas esperadas y en el peor de los casos. Compara montículos binarios, izquierdistas y de emparejamiento (pairing heaps) según la carga de trabajo.

Preguntas de aclaración para hacer

• ¿Consume meld sus montículos de entrada, o deben ambos montículos originales permanecer utilizables?
• ¿Se puede inyectar la fuente aleatoria para que los fallos sean reproducibles?
• ¿Cuáles son el límite de nodos y el presupuesto del stack de recursión?
• ¿Se requieren identificadores estables (stable handles), eliminación arbitraria o decrease-key?
• ¿El objetivo es una implementación pedagógica, rendimiento en producción o una cota estricta para el peor de los casos?

Estructura de respuesta de 30 segundos

“Cada nodo almacena una clave, un valor y dos punteros a hijos. meld(a,b) maneja árboles vacíos, conserva la raíz más pequeña y luego fusiona aleatoriamente el otro árbol en el hijo izquierdo o derecho. insert fusiona un nodo individual con la raíz, y extract-min fusiona los hijos de la raíz eliminada. La raíz permanece mínima y las operaciones suelen tomar tiempo logarítmico esperado, pero la profundidad de recursión y las semillas aleatorias requieren pruebas y límites explícitos.”

Respuesta detallada paso a paso

Paso 1: Definir nodos y propiedad

Almacena key, value, left y right en cada nodo. El montículo almacena su raíz y el conteo de nodos. Con una implementación mutable, meld reconecta las raíces de entrada, por lo que la API debe indicar si las entradas se consumen. Una implementación persistente copia la ruta y, por lo tanto, cambia los costos de tiempo y espacio.

meld(a, b):
  if a is empty: return b
  if b is empty: return a
  if b.key < a.key: swap(a, b)
  if randomBit() == 0:
    a.left = meld(a.left, b)
  else:
    a.right = meld(a.right, b)
  return a

Paso 2: Preservar el invariante de fusión (Meld)

Compara las raíces primero y conserva la clave más pequeña como raíz. Las claves iguales pueden usar una regla de desempate fija o una regla aleatoria, pero el orden de montículo debe seguir siendo válido. Después de que la recursión retorna, cada clave en el hijo fusionado es al menos igual a la raíz actual, por lo que el invariante se mantiene a lo largo de la ruta.

No conectes un nodo a dos padres. Un meld mutable debe rastrear la propiedad; una compilación de depuración puede verificar conteos y ciclos. Una implementación persistente no puede mutar un subárbol compartido.

Paso 3: Implementar Insert y Find-Min

insert crea un nodo individual y lo fusiona con la raíz actual, luego incrementa el conteo. find-min lee la raíz; un montículo vacío sigue el contrato de la interfaz devolviendo un resultado vacío o un error. Las claves duplicadas se mantienen como entradas separadas.

Una fuente aleatoria global dificulta la reproducción de pruebas. Inyecta una fuente aleatoria y usa una semilla fija en las pruebas; producción aún necesita una implementación de bits aleatorios imparcial e independiente.

Paso 4: Implementar Extract-Min

Tras eliminar la raíz, fusiona sus subárboles izquierdo y derecho para formar la nueva raíz. Desvincula ambos punteros antes de decrementar el conteo; si el montículo gestiona la memoria, libera la raíz anterior al final. Cuando las entradas se consumen, invalida los identificadores a la raíz eliminada.

Si las versiones antiguas deben permanecer utilizables, utiliza copia de rutas (path copying) persistente en lugar de mutar nodos compartidos. Declara esto en el límite de la interfaz, ya que el aliasing puede corromper silenciosamente los datos de lo contrario.

Paso 5: Declarar los límites de complejidad

Para un montículo fusionable aleatorizado, meld, insert y extract-min comúnmente se analizan como de tiempo logarítmico esperado o logarítmico con alta probabilidad bajo modelos aleatorios definidos. find-min toma tiempo constante, y el espacio es lineal en el número de nodos.

No conviertas una cota esperada en una afirmación de peor caso por operación. Una secuencia aleatoria desafortunada puede producir un árbol profundo. El código de producción debe limitar la recursión, usar una pila explícita cuando sea necesario y validar la distribución con benchmarks y pruebas aleatorizadas.

Paso 6: Probar contra una referencia

Realiza pruebas diferenciales contra una cola de prioridad estándar con montículos vacíos, claves duplicadas, fusiones alternadas, extracciones repetidas, semillas fijas y extremos de profundidad. Después de cada operación, verifica la raíz mínima, el conteo de nodos, la aciclicidad y las reglas de propiedad.

A diferencia de un pairing heap, este diseño utiliza un árbol binario y ramas aleatorias, por lo que no necesita listas de hermanos, combinación en dos pasadas ni cortes de identificadores. A diferencia de un leftist heap, omite los metadatos de rango y utiliza análisis probabilístico. Analiza la localidad de caché, la mutación y los requisitos de demostración en conjunto.

Ejemplo de respuesta de alta calidad

Mantengo la clave más pequeña en la raíz. meld devuelve el árbol no vacío, intercambia las raíces para que a sea menor, y fusiona aleatoriamente b dentro de a.left o a.right. Tanto insert como extract-min reutilizan meld, mientras que find-min lee la raíz. Primero aclaro si meld consume las entradas; luego inyecto una fuente aleatoria determinista para pruebas diferenciales, comprobando ciclos, conteos, propiedad y orden de la raíz. Describo cotas logarítmicas esperadas o de alta probabilidad bajo el modelo aleatorio y manejo la profundidad de recursión por separado.

Errores comunes

• Aleatorizar antes de comparar raíces → la raíz resultante puede ser demasiado grande → intercambia las raíces primero, luego elige un hijo.
• Reutilizar un montículo mutable antiguo después de meld → un nodo obtiene dos padres → indica el consumo o implementa persistencia.
• Llamar a una cota esperada O(log n) en el peor de los casos → la suposición de probabilidad desaparece → especifica el modelo aleatorio y el calificador de alta probabilidad.
• Usar una fuente aleatoria no inyectable → los fallos no se pueden reproducir → inyéctala y fija la semilla en las pruebas.
• Ignorar la profundidad de recursión → un árbol extremo puede agotar la pila de llamadas → usa una pila explícita, monitorea la profundidad o documenta los límites.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Cómo haces que las pruebas sean deterministas?

Haz que el generador de bits aleatorios sea una dependencia del montículo. Las pruebas proporcionan una secuencia fija o semilla, mientras que producción usa una instancia independiente para que el estado aleatorio global no acople los casos de prueba.

Pregunta de seguimiento 2: ¿Qué pasa si meld debe preservar ambas entradas?

Utiliza una implementación persistente con copia de rutas y subárboles no modificados compartidos. Actualiza la cota de espacio y el plan de liberación de memoria; no afirmes espacio adicional constante para una fusión in-place.

Pregunta de seguimiento 3: ¿Qué pasa si ambos montículos hacen referencia al mismo nodo?

Una API mutable debe rechazar compartir nodos entre montículos y registrar la propiedad en compilaciones de depuración. Una API persistente puede compartir estructuras solo cuando los nodos son inmutables. Devuelve un error de propiedad en lugar de reparar silenciosamente el alias.

Pregunta de seguimiento 4: ¿Por qué no usar un pairing heap?

Un pairing heap se adapta a cargas de trabajo que requieren decrease-key, pero mantiene listas de hijos multivia y reestructuración en eliminación. Un montículo fusionable aleatorizado tiene un meld binario más corto para cargas de trabajo que necesitan fusionar, insertar y eliminar el mínimo mientras aceptan garantías probabilísticas.