Entrevista de código: Implementar un radix heap de enteros monótonos

Planteamiento y casos de uso

Un radix heap es una estructura de enteros para colas de prioridad monótonas, útil en algoritmos como Dijkstra donde las claves extraídas son no decrecientes. Utiliza la última clave extraída como límite y clasifica en cubetas según el bit de mayor diferencia.

Qué evalúa el entrevistador

• Si las claves insertadas están restringidas por la última clave extraída.
• Si el bit de mayor diferencia y el rango de cubetas son correctos.
• Si la cubeta no vacía más pequeña se redistribuye con una nueva base.
• Si se mantienen los invariantes de cubetas y de clave mínima.
• Si se gestionan las colas vacías, el desbordamiento y las claves regresivas.
• Si se explican honestamente la redistribución y la complejidad amortizada.

Aclaraciones antes de responder

• ¿Son las claves enteros sin signo de ancho fijo o de precisión arbitraria?
• ¿Puede una clave insertada ser menor que la última clave extraída?
• ¿Deben ser estables las cargas útiles con claves iguales?
• ¿Solo se requiere pop-min, o también decrease-key y eliminación?
• ¿Qué deben retornar pop sobre vacío y el desbordamiento?
• ¿Es la prioridad la claridad, un factor constante bajo o el límite asintótico?

Estructura de respuesta de 30 segundos

“Mantengo last, la clave extraída más recientemente, y cubetas W+1. Una clave igual a last va a la cubeta 0; de lo contrario, su cubeta es bit_length(key XOR last). Si la cubeta 0 está vacía, busco la cubeta no vacía más pequeña, escaneo su clave mínima como el nuevo last, redistribuyo esa cubeta y hago pop desde la cubeta 0. Se rechaza cualquier clave inferior a last.”

Análisis detallado paso a paso

Paso 1: Establecer invariantes. last nunca disminuye, cada clave pendiente satisface key >= last, y la cubeta i contiene claves cuyo bit de mayor diferencia con respecto a last es i.

Paso 2: Calcular la cubeta. El índice es 0 cuando key == last; de lo contrario, use bit_length(key XOR last). Una clave de W bits necesita cubetas W+1.

Paso 3: Implementar push. Verifique la no negatividad, el ancho y key >= last, luego coloque (key, value) en su cubeta; las claves iguales pueden coexistir.

Paso 4: Implementar pop. Retorne de la cubeta 0 cuando no esté vacía. De lo contrario, busque la cubeta no vacía más baja, escanee su clave mínima y asígnela a last.

Paso 5: Redistribuir. Vacíe esa cubeta y vuelva a calcular el índice de cada elemento respecto al nuevo last; los índices disminuyen y al menos un elemento llega a la cubeta 0.

Paso 6: Manejar límites. Retorne el resultado vacío definido; rechace claves fuera del ancho o por debajo de last para evitar comportamientos no definidos de XOR y de índices.

Paso 7: Establecer complejidad. Cada elemento se redistribuye un número de veces acotado por el tamaño de palabra W; el costo amortizado común es O(W), el espacio es O(n + W), y no es universalmente más rápido que un binary heap.

Respuesta modelo de alta calidad

“Utilizo claves sin signo de 64 bits y 65 cubetas. last comienza en cero; se rechaza una clave por debajo de last, de lo contrario bit_length(key XOR last) selecciona su cubeta. pop toma de la cubeta 0, o encuentra la cubeta no vacía más baja, escanea su clave mínima en last y redistribuye. Las claves iguales mantienen cargas útiles separadas. Pop sobre vacío retorna un valor vacío, y el desbordamiento o las claves regresivas fallan. Cada elemento se redistribuye solo un número de veces acotado por el tamaño de palabra, con espacio para elementos más cubetas.”

Errores comunes

• Permitir claves regresivas → fallan los invariantes de las cubetas → rechazar key < last.
• Usar log2(key) para la cubeta → se ignora la base actual → usar key XOR last.
• Mantener last sin cambios tras la redistribución → la extracción puede ser incorrecta → escanear el mínimo primero.
• Tomar el primer elemento de una cubeta → puede no ser el mínimo → escanear para encontrar la clave mínima.
• Afirmar que cada operación es O(1) → se ignoran el tamaño de palabra y la redistribución → especificar los supuestos de W y amortización.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Por qué se adapta a Dijkstra?

Las distancias extraídas son no decrecientes y las nuevas distancias candidatas no son menores que el mínimo actual, cumpliendo con el requisito de claves monótonas.

Pregunta de seguimiento 2: ¿Qué sucede si se requiere decrease-key arbitrario?

Un radix heap no es adecuado para claves regresivas. Utilice un binary heap o pairing heap, o mantenga versiones y descarte entradas obsoletas de forma perezosa (lazy).

Pregunta de seguimiento 3: ¿Por qué la cubeta 0 puede extraerse (pop) directamente?

Cada clave en la cubeta 0 es igual a last, por lo que todas son claves mínimas actuales.

Pregunta de seguimiento 4: ¿Por qué disminuyen los índices redistribuidos?

El nuevo last es el mínimo de la cubeta; el bit de mayor diferencia de cualquier otro elemento no es mayor que el índice de la cubeta anterior, y al menos uno llega a la cubeta 0.

Pregunta de seguimiento 5: ¿Cómo se mantiene la estabilidad de claves iguales?

Añada un número de secuencia monótono a la carga útil y elija (key, sequence) en la cubeta 0; de lo contrario, la estabilidad es opcional.

Pregunta de seguimiento 6: ¿Qué ocurre con las claves negativas?

Asócielas a un espacio ordenado sin signo o especifique únicamente claves no negativas. El XOR con signo sin una definición de orden no es seguro.

Pregunta de seguimiento 7: ¿Cuándo es mejor un binary heap?

Utilícelo cuando las claves no sean enteros monótonos, el tamaño de palabra sea grande, las actualizaciones sean complejas, o la simplicidad y generalidad importen más que el límite especializado.