Monticulo Binario
Descripcion del TAD
Min-heap representado en arreglo y visualizado tambien como arbol casi completo. En cada operacion identifica los intercambios ascendentes/descendentes que restauran la propiedad: todo padre debe ser menor o igual que sus hijos. El Monticulo Binario (min-heap) se almacena en arreglo y se visualiza como arbol casi completo. Cada operacion aplica sift-up o sift-down para restaurar la propiedad de heap.
Guía de aprendizaje
Objetivo: Predecir ascenso, descenso e intercambio mediante índices.
Estrategia: Mantener forma completa en arreglo y reparar prioridad padre-hijos.
Invariante: A[parent(i)] ≤ A[i] para todo i > 0.
Memoria C: El arreglo representa niveles; no usa enlaces de búsqueda.
Complejidad: Raíz O(1), insertar y extraer O(log n).
Errores frecuentes
- Tratar el heap como ABB.
- Esperar que el arreglo esté totalmente ordenado.
Glosario jerárquico
- Raíz
- Nodo sin padre.
- Hoja
- Nodo sin hijos.
- Altura
- Longitud del camino máximo hacia una hoja.
- Profundidad
- Distancia desde la raíz.
- FE
- Diferencia de alturas entre subárboles.
- Rotación
- Cambio local de enlaces que conserva el orden.
- Recoloreo
- Cambio de colores para reparar reglas rojo-negro.
- Black-height
- Cantidad de nodos negros por camino hasta NIL.
- Heapify
- Proceso de restaurar la propiedad de heap.
Controles de ejecucion paso a paso
- Checkbox Interpretar codigo paso a paso: activado muestra toda la traza; desactivado aplica solo el resultado final.
- Botones: Preparar, Reproducir, Pausar, Inicio, Anterior, Siguiente, Final y Repetir.
- Navegacion por traza: Anterior paso y Siguiente paso.
- Velocidad de simulacion: slider de -2x a +2x (0.00x = 1.00x real).
- En modo rapido (checkbox desactivado), el resultado visual final debe coincidir con el ultimo estado de la traza interpretada.
- Al llegar al ultimo paso, Siguiente paso se bloquea hasta cambiar entradas/operacion; Anterior paso se habilita solo cuando ya avanzaste.
Teclado y accesibilidad
- ←/→: retroceder o avanzar.
- Inicio/Fin: primer o último estado.
- Espacio: pausar.
- Los colores, rotaciones e invariantes incluyen texto y símbolos; con movimiento reducido se desactivan transiciones prolongadas.
Operaciones soportadas
- heapify_up
- heapify_down
- monticulo_raiz
- monticulo_copiar_valores
- monticulo_destruir
Operaciones pendientes / restricciones
- No existe en el TAD una operacion publica para cambiar a max-heap en caliente.
Estructura del TAD en C
typedef enum {
MONTICULO_MIN = 0,
MONTICULO_MAX = 1
} TipoMonticulo;
typedef struct {
int *datos;
int cantidad;
int capacidad;
TipoMonticulo tipo;
} MonticuloBinario;
Metodos del TAD en C
Codigo C: insertar
Inserta respetando reglas de orden/balance del TAD y actualiza punteros estructurales necesarios.
/**
* @brief Restaura la propiedad del montículo moviendo un elemento hacia arriba.
*
* @details Compara el elemento en el `indice` dado con su padre. Si tiene mayor
* prioridad (según `comparar`), los intercambia y repite el proceso.
*
* @param[in,out] m Puntero al montículo.
* @param[in] indice Índice del elemento que se va a subir.
*
* @note Complejidad temporal: O(log N).
*/
static void heapify_up(MonticuloBinario *m, int indice) {
int padre = (indice - 1) / 2;
while (indice > 0 && comparar(m->tipo, m->datos[indice], m->datos[padre])) {
intercambiar(&m->datos[indice], &m->datos[padre]);
indice = padre;
padre = (indice - 1) / 2;
}
}
/**
* @brief Inserta un valor en el montículo preservando su propiedad.
*
* @details Si se alcanza la capacidad máxima del arreglo interno, este se
* redimensiona al doble automáticamente utilizando `realloc`.
*
* @param[in,out] m Puntero al montículo.
* @param[in] valor Valor entero a insertar.
*
* @return @c true si la inserción fue exitosa.
* @return @c false si hubo un error de memoria o `m` es nulo.
*
* @note Complejidad temporal: O(log N) promedio, O(N) si requiere redimensionar.
*/
bool monticulo_insertar(MonticuloBinario *m, int valor) {
if (m == NULL) return false;
if (!asegurar_capacidad(m, m->cantidad + 1)) {
return false;
}
m->datos[m->cantidad] = valor;
heapify_up(m, m->cantidad);
m->cantidad++;
return true;
}
Codigo C: extraer_raiz
Este metodo del TAD Monticulo Binario debe interpretarse respetando condicionales, ciclos, returns y actualizacion del estado visual segun el flujo real del codigo C.
/**
* @brief Restaura la propiedad del montículo hundiendo un elemento hacia abajo.
*
* @details Compara el elemento con sus dos hijos. Si alguno de los hijos tiene
* mayor prioridad, intercambia el elemento con el hijo más prioritario
* y repite el proceso hacia abajo.
*
* @param[in,out] m Puntero al montículo.
* @param[in] indice Índice del elemento que se va a hundir.
*
* @note Complejidad temporal: O(log N).
*/
static void heapify_down(MonticuloBinario *m, int indice) {
int hijo_izq, hijo_der, seleccionado;
while (1) {
hijo_izq = 2 * indice + 1;
hijo_der = 2 * indice + 2;
seleccionado = indice;
if (hijo_izq < m->cantidad && comparar(m->tipo, m->datos[hijo_izq], m->datos[seleccionado])) {
seleccionado = hijo_izq;
}
if (hijo_der < m->cantidad && comparar(m->tipo, m->datos[hijo_der], m->datos[seleccionado])) {
seleccionado = hijo_der;
}
if (seleccionado != indice) {
intercambiar(&m->datos[indice], &m->datos[seleccionado]);
indice = seleccionado;
} else {
break;
}
}
}
/**
* @brief Extrae la raíz del montículo (el menor o mayor elemento según el tipo).
*
* @details Retorna la raíz, la reemplaza por el último elemento del árbol
* y restablece la propiedad hundiendo este nuevo elemento.
*
* @param[in,out] m Puntero al montículo.
* @param[out] resultado Puntero donde se escribirá el valor extraído.
*
* @return @c true si se extrajo correctamente.
* @c false si el montículo está vacío o nulo.
*
* @note Complejidad temporal: O(log N).
*/
bool monticulo_extraer_raiz(MonticuloBinario *m, int *resultado) {
if (m == NULL || m->cantidad == 0 || resultado == NULL) return false;
*resultado = m->datos[0];
m->cantidad--;
if (m->cantidad > 0) {
m->datos[0] = m->datos[m->cantidad];
heapify_down(m, 0);
}
return true;
}
Codigo C: raiz
Retorna el valor de la raiz o tope logico de la estructura sin mutarla.
/**
* @brief Consulta la raíz del montículo sin modificar la estructura.
*
* @param[in] m Puntero constante al montículo.
* @param[out] resultado Puntero donde se almacenará el valor de la raíz.
*
* @return @c true si el montículo no está vacío y se obtuvo el resultado.
* @c false si está vacío o los punteros son nulos.
*
* @note Complejidad temporal: O(1).
*/
bool monticulo_raiz(const MonticuloBinario *m, int *resultado) {
if (m == NULL || m->cantidad == 0 || resultado == NULL) return false;
*resultado = m->datos[0];
return true;
}
Codigo C: a_lista
Exporta el contenido interno a una representacion lineal para inspeccion externa.
/* Copia didactica del arreglo interno del monticulo. */
int buffer[256];
int usados = monticulo_copiar_valores(&monticulo, buffer, 256);
for (int i = 0; i < usados; i++) {
/* buffer[i] contiene el valor en el indice i */
}
Codigo C: limpiar
Recorre la estructura liberando todos los nodos y deja el puntero raiz en estado nulo para reinicio seguro.
/**
* @brief Libera completamente la memoria reservada por el montículo.
*
* @param[in,out] m Puntero al montículo a destruir.
*
* @note Tras ejecutarse, la cantidad y la capacidad se reinician a 0.
* @note Complejidad temporal: O(1).
*/
void monticulo_destruir(MonticuloBinario *m) {
if (m != NULL) {
if (m->datos) {
free(m->datos);
m->datos = NULL;
}
m->cantidad = 0;
m->capacidad = 0;
}
}
/* Reinicio recomendado del TAD tras liberar memoria interna */
/**
* @brief Inicializa un montículo vacío con una capacidad inicial y un tipo.
*
* @param[out] m Puntero al montículo a inicializar.
* @param[in] tipo Tipo de montículo (`MONTICULO_MIN` o `MONTICULO_MAX`).
* @param[in] capacidad_inicial Capacidad base a reservar en el arreglo. Si es <= 0, se usa 10 por defecto.
*
* @note Complejidad temporal: O(1).
*/
void monticulo_inicializar(MonticuloBinario *m, TipoMonticulo tipo, int capacidad_inicial) {
int capacidad_objetivo;
if (m == NULL) return;
m->tipo = tipo;
m->cantidad = 0;
m->capacidad = 0;
m->datos = NULL;
capacidad_objetivo = (capacidad_inicial > 0) ? capacidad_inicial : MONTICULO_CAPACIDAD_POR_DEFECTO;
if (!asegurar_capacidad(m, capacidad_objetivo)) {
m->capacidad = 0;
}
}