⛰️ Montículo Binario — Cola de Prioridad

¿Por qué puede almacenarse un montículo binario en un arreglo sin punteros?

Porque es un árbol binario completo, lleno nivel por nivel sin huecos, el padre y los hijos de un nodo pueden calcularse directamente a partir de su índice en el arreglo (padre = ⌊(i−1)/2⌋, hijos = 2i+1 y 2i+2). Esto evita la sobrecarga de memoria de los nodos de árbol basados en punteros y ofrece una excelente localidad de caché en comparación con las estructuras enlazadas.

¿Cuál es la diferencia de complejidad temporal entre el ascenso y el descenso?

Ambos se ejecutan en O(log n) en el peor caso, ya que cada uno sigue solo un único camino de raíz a hoja de longitud ⌊log₂ n⌋. El ascenso hace como máximo una comparación por nivel contra el padre, mientras que el descenso hace hasta dos comparaciones por nivel contra ambos hijos, por lo que el descenso tiene un factor constante ligeramente mayor a pesar de compartir la misma cota asintótica.

¿Por qué construir un montículo a partir de n elementos es O(n) en lugar de O(n log n)?

El algoritmo de construcción de montículos de Floyd llama al descenso solo en los nodos internos, comenzando desde el último y subiendo hasta la raíz. La mayoría de los nodos están cerca de la parte inferior del árbol, donde un descenso solo puede recorrer una distancia corta; sumar el trabajo en todos los niveles da una serie geométrica que converge a O(n), a diferencia del costo O(n log n) de insertar n elementos uno a uno.

¿Cuál es la diferencia entre un montículo mínimo y uno máximo, y cómo se compara un montículo con un ABB equilibrado para una cola de prioridad?

Un montículo mínimo mantiene el valor más pequeño en la raíz (padre ≤ hijos); un montículo máximo mantiene el más grande (padre ≥ hijos) — se aplican los mismos algoritmos con la comparación invertida. Comparado con un árbol binario de búsqueda equilibrado, un montículo ofrece la misma inserción O(log n) y extracción del mínimo O(log n), pero con una implementación más simple basada en arreglos, sin lógica de reequilibrio, y una consulta O(1) del mínimo, mientras que un ABB ofrece recorrido ordenado y búsqueda O(log n) de claves arbitrarias que un montículo no soporta.