La Torre sin Sueño

En la Torre sin Sueño, ningún habitante osa ordenar por completo el Registro de las Profundidades: hacerlo, dicen, revela un patrón que ninguna mente debería contemplar entero. Y sin embargo, la Orden del Ojo que Vela necesita, en todo momento, saber cuál es la amenaza más urgente entre miles. El Archivista Insomne, que no duerme desde que aceptó el cargo, resolvió ese dilema hace siglos: no hace falta conocer el orden completo de los horrores. Alcanza con poder llegar siempre, al instante, al peor de ellos.

Este sendero te va a enseñar a sostener ese orden parcial (ni caos, ni orden total) usando heap y priority queue. Hay ejercicios de diseño, otros de seguimiento a mano, y uno que pone a prueba tu intuición sobre la complejidad: la cuenta “obvia” no siempre es la que corresponde.

El Presagio que Ascendió
Dificultad: ★☆☆☆☆

Cada vez que una nueva pesadilla toca las puertas de la Torre, un aprendiz debe anotar su nivel de amenaza y ubicarla en el Registro de las Profundidades sin desordenar lo ya construido. La regla es simple y absoluta: lo más terrible siempre tiene que poder alcanzarse en un instante, sin recorrer el registro entero. Esta noche llegaron cinco presagios, uno detrás del otro, y te toca a vos acomodarlos.

Enunciado

El Registro es un montículo binario de máximos (max-heap), representado como un arreglo.

Explicar cómo se representa un montículo binario en un arreglo: dar las fórmulas para calcular el padre y los hijos de una posición i, y justificar por qué esta representación implícita ahorra memoria frente a un árbol con nodos y punteros.

Describir en palabras el algoritmo de inserción con ascenso (sift-up / bubble-up): dónde se coloca el nuevo elemento y cómo se restaura la propiedad de montículo.

Trazar a mano la inserción secuencial de los presagios [15, 8, 21, 4, 30] en un montículo inicialmente vacío, mostrando el arreglo completo después de cada inserción.

Determinar la complejidad de una única inserción en función de la altura del árbol, y justificar por qué esa altura es $O (lo g n)$ para un árbol binario completo.

Susurro del Archivista Insomne. Pensá el arreglo como si fuera el árbol recorrido nivel por nivel, de izquierda a derecha. Si una amenaza está en la posición i (contando desde 0), sus hijos están en 2i+1 y 2i+2, y su padre en (i-1)//2. El ascenso compara la nueva amenaza con su padre: mientras sea más terrible que él, intercambian de lugar.

Reflexión. La propiedad de montículo dice que un padre es siempre más terrible (o igual) que sus hijos. Sin embargo, eso no implica que el arreglo esté ordenado de mayor a menor. Construí un contraejemplo concreto con 4 o 5 elementos: un arreglo que cumpla la propiedad de montículo pero que, leído de izquierda a derecha, no esté ordenado.

Abrir artículo

El Destierro del Horror Mayor
Dificultad: ★★☆☆☆

Cuando se acerca el amanecer, la Orden debe enfrentar a la amenaza más peligrosa registrada hasta el momento y desterrarla, para que la Torre pueda respirar un día más. Pero el Registro no puede quedar vacío en su cima: algo debe ocupar ese lugar, y ese algo tiene que abrirse paso hacia abajo hasta encontrar su verdadero sitio.

Enunciado

Describir en palabras el algoritmo de extracción del máximo (extract-max): qué se hace con el último elemento del arreglo y cómo se restaura la propiedad de montículo mediante descenso (sift-down / heapify-down).

Trazar a mano extract-max sobre el montículo [30, 21, 15, 4, 8, 12, 9], mostrando el arreglo completo después de cada paso del descenso.

Determinar y justificar la complejidad de una extracción, relacionándola con la altura del árbol (de la misma forma que analizaste la inserción en el Ejercicio 1, pero ahora para el descenso).

Completar la siguiente tabla con la complejidad de cada operación para tres estructuras distintas, y estar preparado para justificar cada celda:

Estructura Encontrar el máximo Insertar Extraer el máximo
Arreglo sin ordenar
Arreglo ordenado
Montículo (heap)

Susurro del Archivista Insomne. El descenso no es solo “bajar”: en cada nivel hay que elegir con cuál de los dos hijos comparar. Si el nodo es menor que alguno de sus hijos, tiene que intercambiar con el mayor de los dos… si intercambiara con el menor, la propiedad de montículo podría quedar rota un nivel más abajo.

Reflexión. Si la Orden necesitara encontrar la amenaza más peligrosa una sola vez, sin volver a insertar ni a extraer nada más, ¿seguiría siendo el montículo la mejor estructura para el trabajo? ¿Por qué sí o por qué no?

Abrir artículo

La Convocatoria de las Mil Voces
Dificultad: ★★★☆☆

Un sótano olvidado de la Torre entregó un cofre con cientos de presagios nunca catalogados, todos mezclados sin ningún orden. Un aprendiz impaciente propuso insertarlos uno por uno, tal como se enseña siempre; pero el Archivista Insomne, que ha visto cofres como este durante siglos, sonrió con algo parecido a la lástima. Hay una forma más rápida, y nadie que la aprende vuelve a mirar una inserción repetida de la misma manera.

Enunciado

Método ingenuo: insertar los n presagios uno por uno en un montículo inicialmente vacío, como en el Ejercicio 1. ¿Cuál es la complejidad total en el peor caso? Justificar.

Método “desde abajo”: en lugar de insertar de a uno, aplicar sift-down empezando por el último nodo interno del arreglo (el último nodo que tiene al menos un hijo) y retrocediendo hasta la raíz. Describir el algoritmo en palabras. ¿Por qué alcanza con arrancar en el último nodo interno, sin procesar las hojas?

Trazar a mano el método “desde abajo” sobre el arreglo [4, 18, 9, 25, 1, 30, 12, 7, 22, 15], mostrando el arreglo completo después de aplicar sift-down sobre cada nodo interno procesado.

Formalizar el argumento de complejidad del método “desde abajo”: plantear la suma que acota el costo total, pensando en cuántos nodos hay a cada altura del árbol y cuánto cuesta el sift-down de un nodo según su altura. Mostrar que esa suma converge a $O (n)$ . (No hace falta una demostración completamente rigurosa, pero sí identificar la serie involucrada y explicar por qué converge a una constante.)

Susurro del Archivista Insomne. Un montículo de n elementos tiene aproximadamente n/2 hojas (altura 0, costo de sift-down nulo), n/4 nodos de altura 1, n/8 de altura 2, y así sucesivamente. El costo de sift-down sobre un nodo depende de la altura de ese nodo, no de la altura total del árbol. Sumá, para cada altura, la cantidad de nodos que hay multiplicada por el costo de esa altura.

Reflexión Trampa. Reconciliá tu resultado del punto 4 con este razonamiento, que suena razonable pero no lo es: “El método ‘desde abajo’ hace del orden de n operaciones de sift-down, cada una de costo hasta $O (lo g n)$ en el peor caso… eso debería dar $O (n lo g n)$ en total, igual que insertar uno por uno.” ¿Dónde está el error de esa cuenta? ¿Por qué sobreestima el costo real?

Ver solución

1. Método ingenuo

Insertar el $k$ -ésimo elemento en un montículo que ya tiene $k - 1$ elementos cuesta, en el peor caso, un sift-up que recorre la altura del árbol: $O (lo g k)$ .
$T (n) = k = 1 \sum n O (lo g k) = O (lo g (n!)) = O (n lo g n)$
(por la aproximación de Stirling, o simplemente porque cada una de las $n$ inserciones cuesta a lo sumo $O (lo g n)$ ). Cota ajustada, porque las últimas $n /2$ inserciones ocurren efectivamente sobre montículos de tamaño $Θ (n)$ , con altura real $Θ (lo g n)$ .

2. Método “desde abajo”

Idea: en vez de construir el montículo agregando hojas y arreglando hacia arriba, se parte del arreglo tal cual y se “arregla hacia abajo” cada subárbol, de atrás para adelante.

Algoritmo:

Ubicar el último nodo interno: índice $⌊ n /2 ⌋ - 1$ (0-indexado).

Para $i$ desde ese índice hasta $0$ : aplicar sift-down(i).

Por qué no hace falta procesar las hojas: un sift-down compara un nodo contra sus hijos y hunde el valor si corresponde. Una hoja no tiene hijos, así que sift-down sobre una hoja es una operación vacía: cada hoja ya es, trivialmente, un montículo válido de un solo elemento. Además, el invariante clave es que cuando se procesa el nodo $i$ , sus dos subárboles hijos ya son montículos válidos (porque se procesaron antes, al ir de atrás hacia adelante); eso es justamente lo que garantiza la corrección de sift-down(i).

3. Traza

Sobre [4, 18, 9, 25, 1, 30, 12, 7, 22, 15]:

$n = 10$ , índices $0$ – $9$ . Último nodo interno: $⌊ 10/2 ⌋ - 1 = 4$ .

Nodo procesado (índice : valor) Hijos comparados Arreglo resultante
inicial ∅ [4,18,9,25,1,30,12,7,22,15]
$4 : 1$ hijo(9)=15 [4,18,9,25,15,30,12,7,22,1]
$3 : 25$ hijos(7)=7,(8)=22 → no baja [4,18,9,25,15,30,12,7,22,1]
$2 : 9$ hijos(5)=30,(6)=12 → baja con 30 [4,18,30,25,15,9,12,7,22,1]
$1 : 18$ hijos(3)=25,(4)=15 → baja con 25; sigue: hijos(7)=7,(8)=22 → baja con 22 [4,25,30,22,15,9,12,7,18,1]
$0 : 4$ hijos(1)=25,(2)=30 → baja con 30; sigue: hijos(5)=9,(6)=12 → baja con 12 [30,25,12,22,15,9,4,7,18,1]

Resultado final: [30, 25, 12, 22, 15, 9, 4, 7, 18, 1] (se verifica la propiedad de montículo en cada nodo).

4. Complejidad del método “desde abajo”

El costo de sift-down en un nodo depende de la altura de ese nodo (distancia hasta su hoja más lejana), no de la altura del árbol completo. Como sugiere el Archivista:

Altura $h$ # nodos $\approx n / 2^{h + 1}$ costo por nodo contribución
$0$ $n /2$ $O (1)$ (trivial) $0$
$1$ $n /4$ $O (1)$ $\propto n /4$
$2$ $n /8$ $O (2)$ $\propto 2 n /8$
$⋮$ $⋮$ $⋮$ $⋮$
$h$ $n / 2^{h + 1}$ $O (h)$ $\propto h n / 2^{h + 1}$

Sumando sobre todas las alturas ( $h = 0, \dots, ⌊ lo g n ⌋$ ):
$T (n) = h = 0 \sum l o g n \frac{n}{2 ^{h + 1}} \cdot O (h) = O (n) h = 0 \sum \infty \frac{h}{2 ^{h}}$
La serie $\sum_{h = 0}^{\infty} h / 2^{h}$ es una serie aritmético-geométrica: converge (porque $1/2 < 1$ ) a un valor constante:
$h = 0 \sum \infty \frac{h}{2 ^{h}} = 2$
Por lo tanto $T (n) = O (n) \cdot 2 = O (n)$ . La clave es que la cantidad de nodos decrece exponencialmente a medida que crece su costo, así que el producto (nodos × costo) decrece también exponencialmente y la suma total queda acotada por una constante multiplicando $n$ .

Respuesta a la reflexión trampa

El error de ” $n$ operaciones × $O (lo g n)$ cada una = $O (n lo g n)$ ” es multiplicar por la cota superior global ( $O (lo g n)$ , que solo corresponde al nodo raíz) en vez de usar el costo real de cada nodo según su altura.

Casi todos los nodos ( $n /2$ ) son hojas con costo $0$ , y la mitad de los internos ( $n /4$ ) tienen altura $1$ con costo $O (1)$ . Solo hay un nodo (la raíz) con costo genuinamente $O (lo g n)$ . Usar $O (lo g n)$ para los $n$ nodos ignora que la mayoría son mucho más baratos, y por eso sobreestima brutalmente.

Esto contrasta con la inserción uno por uno: ahí sí hay $Θ (n)$ inserciones que ocurren sobre montículos de tamaño $Θ (n)$ (las últimas), con costo real $Θ (lo g n)$ cada una. El peor caso no está concentrado en un solo nodo, sino distribuido en una fracción constante de las operaciones. Esa asimetría (dónde se concentran los casos caros) es la diferencia real entre $O (n)$ y $O (n lo g n)$ .

Abrir artículo

Nodo procesado (índice : valor)	Hijos comparados	Arreglo resultante
inicial	∅	`[4,18,9,25,1,30,12,7,22,15]`
$4 : 1$	hijo(9)=15	`[4,18,9,25,15,30,12,7,22,1]`
$3 : 25$	hijos(7)=7,(8)=22 → no baja	`[4,18,9,25,15,30,12,7,22,1]`
$2 : 9$	hijos(5)=30,(6)=12 → baja con 30	`[4,18,30,25,15,9,12,7,22,1]`
$1 : 18$	hijos(3)=25,(4)=15 → baja con 25; sigue: hijos(7)=7,(8)=22 → baja con 22	`[4,25,30,22,15,9,12,7,18,1]`
$0 : 4$	hijos(1)=25,(2)=30 → baja con 30; sigue: hijos(5)=9,(6)=12 → baja con 12	`[30,25,12,22,15,9,4,7,18,1]`

Altura $h$	# nodos $\approx n / 2^{h + 1}$	costo por nodo	contribución
$0$	$n /2$	$O (1)$ (trivial)	$0$
$1$	$n /4$	$O (1)$	$\propto n /4$
$2$	$n /8$	$O (2)$	$\propto 2 n /8$
$⋮$	$⋮$	$⋮$	$⋮$
$h$	$n / 2^{h + 1}$	$O (h)$	$\propto h n / 2^{h + 1}$

Los Cinco Oráculos y el Cómputo de las Sombras
Dificultad: ★★★★☆

Cinco oráculos ciegos susurran presagios sin parar, cada uno en su propio orden creciente de espanto, cada uno ajeno a los demás. La Orden necesita una única secuencia que combine las cinco, sin detener a ningún oráculo y sin volver a ordenar lo que ya venía ordenado. El desorden total sería intolerable; pero reordenar todo desde cero, una herejía innecesaria.

Enunciado

Hay k secuencias, cada una ya ordenada de forma creciente, con n elementos en total entre todas.

Explicar por qué concatenar las k secuencias y volver a ordenar todo con un algoritmo de comparación general no es la mejor estrategia. ¿Cuál sería la complejidad de hacerlo así, en función de k y de n?

Diseñar un algoritmo que combine las k secuencias en una sola, ordenada, usando una cola de prioridad de tamaño k, donde en cada paso se extrae el mínimo actual y se inserta el siguiente elemento de la secuencia de la que provino. Describir el algoritmo paso a paso.

¿Qué información hay que guardar en cada elemento de la cola de prioridad, además del valor del presagio, para saber de qué secuencia vino y cuál es su próximo elemento? Proponer una estructura concreta (por ejemplo, una tupla) para representarlo.

Determinar la complejidad total del algoritmo en función de k y n, y compararla con la del método ingenuo del punto 1.

Trazar a mano el algoritmo con estas tres secuencias:

Oráculo A: [2, 9, 14]

Oráculo B: [4, 5, 20]

Oráculo C: [1, 8, 11, 30]

mostrando el estado de la cola de prioridad y la secuencia de salida generada en cada paso.

Susurro del Archivista Insomne. Cada elemento que sacás de la cola te dice de qué secuencia vino. Apenas lo sacás, insertá el siguiente elemento de esa misma secuencia (si le queda alguno). La cola nunca crece más allá de k elementos, y ahí está la clave de por qué esto sale más barato que juntar y ordenar todo de una vez.

Reflexión. Ahora supongamos que la Orden no necesita las amenazas combinadas y ordenadas por completo, sino solamente las m amenazas más peligrosas de todo el conjunto (con m mucho menor que n), sin importar el orden del resto. ¿Convendría usar una cola de prioridad de tamaño n? ¿De qué tamaño convendría que fuera, y por qué eso cambia el resultado?

Abrir artículo

La Balanza de la Medianoche
Dificultad: ★★★★★

En el centro de la Torre cuelga una balanza que nadie recuerda haber construido. No pesa objetos: pesa presagios, y siempre debe señalar cuál es el nivel de amenaza que divide exactamente a la mitad todo lo registrado hasta el momento (ni más liviano, ni más pesado). Los presagios no dejan de llegar, y la balanza no puede detenerse jamás a reordenar el archivo completo para responder.

Enunciado

El objetivo es mantener la mediana de un flujo de valores que van llegando de a uno, pudiendo consultarla en cualquier momento sin volver a ordenar todo lo recibido hasta ahí.

Explicar la idea general de resolver este problema con dos montículos: uno de máximos, con la mitad “menor” de los valores vistos hasta el momento, y otro de mínimos, con la mitad “mayor”, de forma que la raíz de cada uno quede siempre cerca del centro de la distribución.

Describir el invariante de tamaños que hay que mantener entre ambos montículos después de cada inserción, necesario para poder calcular la mediana en $O (1)$ a partir de sus raíces.

Diseñar el algoritmo de inserción de un nuevo valor: a qué montículo entra primero, en qué condición hay que “pasar” un elemento de un montículo al otro para restaurar el invariante del punto 2, y cómo se calcula la mediana según la paridad de la cantidad total de elementos.

Trazar a mano la inserción, uno por uno, de los presagios [12, 5, 27, 8, 19, 3, 15], mostrando el estado de ambos montículos y la mediana reportada después de cada inserción.

Determinar la complejidad de insertar un nuevo valor y de consultar la mediana, y comparar con la alternativa de mantener en todo momento un arreglo completamente ordenado.

Susurro del Archivista Insomne. Si en algún momento un montículo queda con más de un elemento de diferencia respecto al otro, movés la raíz del más grande hacia el otro. La mediana sale de la raíz del montículo con más elementos (si los tamaños son distintos) o del promedio de ambas raíces (si son iguales).

Reflexión final. ¿Por qué no alcanza con un solo montículo para resolver este problema? ¿Qué información se pierde si se intenta usar únicamente un max-heap, o únicamente un min-heap, con todos los valores adentro?

Abrir artículo

Si este sendero te dejó con ganas de más: la misma idea de “adelantar siempre lo más urgente sin ordenar todo” es el corazón de algoritmos como Dijkstra (caminos mínimos), Prim (árboles de expansión mínima) y la codificación de Huffman. Todos usan una cola de prioridad exactamente como la que construiste acá… solo que las “amenazas” son distancias, pesos, o frecuencias.

Arcana

Explorador

La Torre sin Sueño

El Presagio que Ascendió

El Destierro del Horror Mayor

La Convocatoria de las Mil Voces

1. Método ingenuo

2. Método “desde abajo”

3. Traza

4. Complejidad del método “desde abajo”

Respuesta a la reflexión trampa

Los Cinco Oráculos y el Cómputo de las Sombras

La Balanza de la Medianoche

Vista Gráfica

Retroenlaces