heap.c

#include <stdlib.h>
#include "heap.h"
#define CAPACIDAD_STANDARD 10

void swap(void **a, void **b) {
    void* temp = *a;
    *a = *b;
    *b = temp;
}

typedef struct heap {
    cmp_func_t cmp;
    size_t capacidad; // Representa el largo del datos
    size_t cantidad; // Cantidad de elementos
    void** datos;
} heap_t;

heap_t *heap_crear(cmp_func_t cmp) {
    heap_t* heap = malloc(sizeof (heap_t));
    if (heap == NULL) return NULL;
    heap->capacidad = CAPACIDAD_STANDARD;
    heap->cantidad = 0;
    heap->cmp = cmp;
    heap->datos = malloc (sizeof (void*) * CAPACIDAD_STANDARD);
    if (heap->datos == NULL){
        free(heap);
        return NULL;
    }
    return heap;
}

void heap_redimensionar_datos(heap_t *heap, size_t nuevaCapacidad){
    heap->datos = realloc(heap->datos, sizeof (void*) * nuevaCapacidad);
    if (heap->datos) heap->capacidad = nuevaCapacidad;
}

void downHeap(void** datos, cmp_func_t cmp, size_t cantidad, size_t padre){
    size_t h_izq = 2 * padre + 1;
    size_t h_der = 2 * padre + 2;
    if (h_izq >= cantidad) return;

    size_t min = h_izq;
    if (h_der < cantidad && cmp(datos[h_izq], datos[h_der]) < 0)
        min = h_der;

    if (cmp(datos[min], datos[padre]) > 0){
        swap(&datos[min], &datos[padre]);
        downHeap(datos, cmp, cantidad, min);
    }
}

heap_t *heap_crear_arr(void **arreglo, size_t n, cmp_func_t cmp) {
    heap_t* heap = heap_crear(cmp);
    if (heap == NULL) return NULL;
    for (int i = 0; i < n; i++){
        heap_encolar(heap, arreglo[i]);
    }
    return heap;
}

void heap_destruir(heap_t *heap, void (*destruir_elemento)(void *)) {
    while (!heap_esta_vacio(heap)){
        void* prim = heap_desencolar(heap);
        if (destruir_elemento != NULL) {
            destruir_elemento(prim);
        }
    }
    free(heap->datos);
    free(heap);
}

size_t heap_cantidad(const heap_t *heap) {
    return heap->cantidad;
}

bool heap_esta_vacio(const heap_t *heap) {
    return heap->cantidad == 0;
}

void upHeap(void** datos, cmp_func_t cmp, size_t cantidad, size_t hijo){
    if (hijo == 0) return;
    size_t padre = (hijo-1)/2;
    if (cmp(datos[hijo], datos[padre]) > 0){
        swap(&datos[hijo], &datos[padre]);
        upHeap(datos, cmp, cantidad, padre);
    }
}

bool heap_encolar(heap_t *heap, void *elem) {
    if (heap->cantidad == heap->capacidad){
        heap_redimensionar_datos(heap, heap->capacidad*2);
        if (heap->datos == NULL) return NULL;
    }

    heap->datos[heap->cantidad] = elem;
    upHeap(heap->datos, heap->cmp, heap->cantidad, heap->cantidad);
    heap->cantidad++;
    return true;
}

void *heap_ver_max(const heap_t *heap) {
    return heap->datos[0];
}

void *heap_desencolar(heap_t *heap) {
    if (heap_esta_vacio(heap)) return NULL;

    heap->cantidad--;
    void* dato = heap->datos[0];

    if (heap->cantidad == 1){
        heap->datos[0] = NULL;
        return dato;
    }

    // Paso el ultimo al principio
    heap->datos[0] = heap->datos[heap->cantidad];
    heap->datos[heap->cantidad] = NULL;

    downHeap(heap->datos, heap->cmp, heap->cantidad, 0);

    if (heap->cantidad <= heap->capacidad/4){
        heap_redimensionar_datos(heap, heap->capacidad/2);
        if (heap->datos == NULL) return NULL;
    }

    return dato;
}

void heap_sort(void **elementos, size_t cant, cmp_func_t cmp) {

    for (int i = (int)cant/2-1; i>= 0; i--){
        downHeap(elementos, cmp, cant, i);
    }

    for (int i = (int)cant - 1; i >= 0; i--) {
        swap(&elementos[0], &elementos[i]);
        downHeap(elementos, cmp, i, 0);
    }
}