Laboratorio de árboles y montículos en C

Montículo Binario

Acerca de esta estructura

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

Abrir guía de Montículo Binario

1 Preparar

El nivel cambia la guía de aprendizaje y la explicación del paso; el código C real y la operación son los mismos. Ocultar documentación solo filtra comentarios.

Ejemplos guiados

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

2 Predecir

Prepara una traza para predecir una condición aún no ejecutada.

Practica anticipando una condición C antes de revelar su resultado: elige Insertar y un valor, activa Paso a paso y pulsa Ejecutar operación. Responde Verdadero o Falso; NULL indica ausencia de un nodo referenciado.

Comprobar u omitir avanza varias instrucciones hasta esa decisión; Siguiente paso avanza solo una instrucción. El estado visible es el anterior a la decisión.

Durante un lote, la predicción y los controles individuales quedan bloqueados para no mezclar operaciones. Finaliza el lote o pulsa Detener lote y prepara una operación individual. Detener conserva la operación ya aceptada y descarta las pendientes.

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

3 Ejecutar y visualizar

5 Relacionar con C

Código 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).
 * @pre m y datos validos; indice >= 0 identifica slot inicializado dentro de capacidad (puede ser cantidad antes de incrementarla). Antecesores satisfacen propiedad salvo ese slot.
 * @note No comprueba NULL/limites ni reserva/libera. Compara estrictamente con padres; empates no se intercambian.
 */
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.
 *
 * @details El retorno es estado bool, no el entero insertado. Si m es NULL o
 * falla la reserva, devuelve false sin cambiar datos, cantidad, capacidad ni valores.
 * En exito escribe datos[cantidad], restaura la prioridad con heapify_up y solo
 * entonces incrementa cantidad. La celda escrita aun esta fuera de cantidad durante el ascenso.
 * El intercambio son tres asignaciones, no una mutacion atomica.
 * Un realloc exitoso termina la vida previa aunque reutilice direccion: no evaluar
 * alias anteriores; el temporal se publica en datos antes de asignar capacidad.
 * Si realloc falla, el buffer previo sigue vivo. Las celdas nuevas no se inicializan
 * por realloc; solo la asignacion del valor garantiza esa celda inicializada.
 * @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

Actual: +0.00x (1.00x real)

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

Paso: 0/0

4 Comprender

Referencia completa de la estructura

Min-heap representado en arreglo y visualizado también como árbol casi completo. Ver arreglo copia todos los valores en su orden interno, no en orden total. El main reproducible reserva la copia según la cantidad actual y libera esa memoria; si la reserva falla, termina sin mostrar una copia parcial. Las consultas exitosas repetidas se conservan al recargar; restaurarlas no vuelve a ejecutarlas. En Insertar y Extraer raíz identifica los intercambios que restauran la prioridad padre-hijos. Ver raíz y Ver arreglo son consultas: no intercambian ni modifican el arreglo del montículo. En estas dos consultas, el resaltado corresponde a la instrucción ya ejecutada; retroceder cambia la observación, no vuelve a ejecutar una operación. Ver raíz separa el bool de exito del int de salida, que permanece sin inicializar si falla la guarda. Ver arreglo muestra cada celda del buffer independiente al inicializarse y conserva registros anteriores a free; estos registros no son memoria viva ni punteros utilizables. Los llamadores equivalentes mostrados son auxiliares didácticos, no nuevas funciones del C/H. La capacidad es distinta de cantidad: solicitar 16 reserva 20 según el C (base 10 y duplicación); el elemento 21 hace crecer a 40 y extraer elementos no reduce esa capacidad. La vista muestra los valores lógicos hasta cantidad; no afirma que el espacio restante sea cero. Limpiar destruye el buffer previo aunque cantidad sea cero, asigna datos NULL y luego cantidad y capacidad 0. A continuación inicializa otro buffer: pedir 16 reserva 20 si la reserva tiene exito; si falla, conserva datos NULL, cantidad 0 y capacidad 0. El retorno void no anuncia el resultado de la reserva. La nueva vida A2 es distinta de A1 aunque el asignador reutilice una dirección. A2 nace sin enteros inicializados; las celdas fuera de cantidad en A1 se muestran como no observadas, no como ceros. Retroceder observa registros anteriores, sin ejecutar free ni reservar otra vez. En Insertar, datos[cantidad] se escribe antes del ascenso y cantidad++ ocurre después. Los dibujos siguen las celdas escritas, incluyendo esa celda pendiente fuera de cantidad; no confunden cantidad con celdas escritas. Comparar recibe enteros por valor; intercambiar recibe alias int * y ejecuta temp=*a, *a=*b y *b=temp por separado: hay duplicación transitoria. División entera C trunca hacia cero: (-1)/2 da 0. El cortocircuito evita comparar si índice es 0. Si realloc crece, el buffer previo termina su vida; el nuevo conserva el prefijo y se publica antes de asignar capacidad. Entre esas instrucciones datos es indeterminado y los dibujos se suspenden. Si realloc falla, la inserción devuelve false y conserva contenido/cantidad/capacidad. El bool se muestra al retornar; avanzar o retroceder nunca vuelve a insertar. En Extraer raíz, el entero externo se escribe primero; después disminuye cantidad. Si aún hay elementos, la antigua cola se copia en la raíz antes del descenso. Las dos vistas siguen el prefijo lógico; la tarjeta de memoria conserva la cola inicializada fuera de cantidad, sin dibujarla como otro elemento. No se libera A1 ni se reduce capacidad. Cada hijo se compara solo si está dentro de cantidad; el empate no selecciona ese hijo. El descenso muestra tres escrituras por intercambio. Si el heap está vacío, devuelve false sin escribir salida; no hay descenso. El entero de salida es distinto del bool; retroceder no extrae de nuevo.

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

Elige una pareja o una estructura contra todas. Cada una recibe una copia independiente de la misma entrada inmutable; los pasos corresponden a inserciones completas.

Prepara una comparación para estudiar forma, altura, orden e invariante después de cada inserción.

7 Reflexionar

Ver y copiar main.c

Consola C (printf)

terminal

Programa principal del historial

    Estructura del TAD
    typedef enum {
        MONTICULO_MIN = 0,  /**< Menor valor tiene prioridad; comparacion estricta. */
        MONTICULO_MAX = 1   /**< Mayor valor tiene prioridad; comparacion estricta. */
    } TipoMonticulo;
    
    typedef struct {
        int *datos; /**< Arreglo de datos del montículo. */
        int cantidad; /**< Número de elementos almacenados. */
        int capacidad; /**< Capacidad reservada de la estructura. */
        TipoMonticulo tipo; /**< Tipo de montículo mínimo o máximo. */
    } MonticuloBinario;