Montículo Binario

Laboratorio de árboles y montículos en C

Montículo min-heap representado en arreglo y árbol.

Abrir guía de Montículo Binario

1 Preparar

Los ejemplos construyen el estado mediante operaciones públicas reales.

2 Predecir

Formula una hipótesis antes de revelar el siguiente frame canónico.

Predicción Modo práctica: ocultar siguiente estado

Progreso conceptual de esta sesión: 0 aciertos de 0 intentos.

3 Ejecutar y visualizar

Codigo C: Insertar

/**
 * @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;
}

3 Controlar la ejecución

Interpretar código paso a paso

Velocidad

Actual: +0.00x (1.00x real)

Progreso navegable

Función: — · Profundidad: — · Fase: — · Concepto: —

Paso: 0/0

4 Comprender

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.

Prepara una operación para observar ruta, caso e invariante.

Condición, ruta y caso

Sin frame.

Pila recursiva y retornos

Sin llamadas.

Invariante y evidencia

Sin verificación.

Variables C

Sin variables.

Memoria y enlaces

Sin transición de memoria.

Relaciones estructurales

Sin relaciones.

6 Comparar

Ambos lados reciben copias independientes de la misma entrada inmutable.

Prepara una comparación para estudiar forma, altura, ajustes, costo e invariante.

7 Reflexionar

Consola C (printf)

terminal

Historial

Estructura del TAD

typedef enum {
    MONTICULO_MIN = 0,  
    MONTICULO_MAX = 1   
} TipoMonticulo;

typedef struct {
    int *datos;            
    int cantidad;         
    int capacidad;         
    TipoMonticulo tipo;    
} MonticuloBinario;