Visualizador Web de Estructuras de Datos

Raíz

Nodo sin padre.

Hoja

Nodo sin hijos.

Altura

En ABB, AVL y el auxiliar de Rojo-Negro se cuentan niveles: árbol vacío 0, hoja 1. Revisa la convención de la función que estudias.

Profundidad

Distancia desde la raíz.

FE

Altura del subárbol derecho menos altura del izquierdo.

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.

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;

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

Copia el mínimo a la salida, reduce la cantidad y repara el orden bajando el nuevo valor de la raíz. Distingue el valor extraído del indicador de éxito.

/**
 * @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).
 * @pre m y datos validos; 0 <= indice < cantidad <= capacidad; subarboles de hijos ya son heaps. Cada 2*indice+2 visitado debe ser representable en int.
 * @note No comprueba NULL ni corrige metadata. Compara hijo izquierdo antes de derecho y usa mejora estricta; no reserva/libera. No certifica indices enormes.
 */
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).
 * @details El retorno bool indica estado, no el entero extraido. Si m es NULL,
 * cantidad es cero o resultado es NULL, devuelve false sin escribir la salida
 * ni modificar datos, cantidad o capacidad; la condicion usa cortocircuito.
 * En exito escribe *resultado antes de reducir cantidad. Si queda algun elemento,
 * copia la antigua cola en la raiz y ejecuta heapify_down. Cada intercambio son
 * tres asignaciones independientes: pueden existir valores duplicados transitorios.
 * Extraer no libera ni reduce capacidad; la celda de la antigua cola sigue viva
 * e inicializada fuera del prefijo logico. No se debe mostrar como otro elemento.
 * Las comparaciones reciben enteros por valor; el intercambio usa alias int *.
 */
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;
}

Retorna el valor de la raíz o tope lógico 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).
 * @details Si devuelve false, no escribe resultado. Si devuelve true,
 * escribe el entero de datos[0], distinto del estado booleano retornado.
 * No reserva memoria ni cambia los datos, cantidad o capacidad del monticulo.
 */
bool monticulo_raiz(const MonticuloBinario *m, int *resultado) {
    if (m == NULL || m->cantidad == 0 || resultado == NULL) return false;
    *resultado = m->datos[0];
    return true;
}

Exporta el contenido interno a una representación lineal para inspección externa.

/* Copia didactica del arreglo interno del monticulo. */
/* Requiere <stdlib.h>; reserva solo si hay elementos. */
int cantidad = monticulo_cantidad(&monticulo);
int *buffer = cantidad > 0 ? malloc((size_t)cantidad * sizeof *buffer) : NULL;
if (cantidad > 0 && buffer == NULL) {
    /* Sin memoria: no copiar ni presentar un resultado incompleto. */
    return EXIT_FAILURE;
}
int usados = monticulo_copiar_valores(&monticulo, buffer, cantidad);
for (int i = 0; i < usados; i++) {
    /* buffer[i] contiene el valor en el indice i, no orden total. */
}
free(buffer);

Libera el arreglo interno del montículo y lo reinicializa para volver a operar; este TAD no utiliza nodos enlazados.

/**
 * @brief Libera completamente la memoria reservada por el montículo.
 *
 * @param[in,out] m Puntero al montículo a destruir.
 *
 * @details Si m es NULL no hace nada. Si datos no es NULL libera ese buffer,
 * incluso con cantidad 0, y asigna datos NULL antes de reiniciar los contadores.
 * No modifica tipo. Los alias del buffer liberado no se deben evaluar ni usar.
 * Esta funcion no reinicializa ni reserva memoria: el llamador visible Limpiar
 * invoca despues monticulo_inicializar con capacidad solicitada 16 (reserva 20
 * si tiene exito; si falla, datos NULL y capacidad 0). Es otra vida de memoria.
 * @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.
 * 
 * @pre Estructura escribible sin reserva propietaria pendiente; tamanos de reserva representables en size_t.
 * @note NULL m se ignora. Reinicializar no libera datos anteriores: destruir antes. Fija tipo, cantidad=0 y datos=NULL; capacidad inicial <=0 usa 10.
 * @note Fallo reserva deja cantidad=capacidad=0, datos=NULL, tipo conservado; retorno void no comunica exito. No valida enum.
 * @note La seleccion de capacidad por duplicacion realiza O(log capacidad_objetivo) iteraciones en el peor caso; el coste del allocator no se certifica.
 */
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;
    }
}