heap.c

#include "heap.h"
#include <stdlib.h>

#define POSICION_DEL_MAX 0
#define CANTIDAD_INICIAL 0
#define CAPACIDAD_INICIAL 24
#define REDIMENSIONADOR 2
#define TAMANIO_RELATIVO 4

struct heap{
	void** datos;
	cmp_func_t cmp;
	size_t cantidad;
	size_t capacidad;
};

void _swap(void* datos[], size_t pos_1, size_t pos_2){
	void* aux = datos[pos_1];
	datos[pos_1] = datos[pos_2];
	datos[pos_2] = aux;
}
void _upheap(void *datos[], size_t pos, cmp_func_t cmp){
	if(pos == 0) return;
	size_t padre = (pos-1)/2;

	if(cmp(datos[padre], datos[pos]) > 0) return;

	_swap(datos, padre, pos);
	_upheap(datos,padre,cmp);
}
void _downheap(void *datos[], size_t n, size_t pos, cmp_func_t cmp){

	if(pos >= n) return;

	size_t pos_hijo_izq = 2*pos+1;
	size_t pos_hijo_der = 2*pos+2;
	size_t pos_max = pos;

	if(pos_hijo_izq < n && cmp(datos[pos_hijo_izq], datos[pos_max])>0){
		pos_max = pos_hijo_izq;
	}
	if(pos_hijo_der < n && cmp(datos[pos_hijo_der], datos[pos_max])>0){
		pos_max = pos_hijo_der;
	}
	if(pos != pos_max){
		_swap(datos, pos, pos_max);
		_downheap(datos, n, pos_max, cmp);
	}
}
heap_t* heap_crear(cmp_func_t cmp){

	heap_t* heap = malloc(sizeof(heap_t));

	if (!heap) return NULL;

	heap->cantidad = CANTIDAD_INICIAL;
	heap->capacidad = CAPACIDAD_INICIAL;
	heap->cmp = cmp;

	heap->datos = malloc((heap->capacidad)*sizeof(void*));

	if(!heap->datos){
        free(heap);
        return NULL;
    }
    return heap;
}
heap_t *heap_crear_arr(void *arreglo[], size_t n, cmp_func_t cmp){

	heap_t* heap = heap_crear(cmp);

	if(!heap) return NULL;

	size_t pos_act = 0;

	while(pos_act < n){
		if(!heap_encolar(heap,arreglo[pos_act])){
			heap_destruir(heap, NULL);
			return NULL;
		}
		pos_act++;
	}
	return heap;
}
bool _redimensionar_heap(heap_t *heap, size_t tam_nuevo){

	void** datos_nuevos = realloc(heap->datos, tam_nuevo*sizeof(void*));

	if(!tam_nuevo) return false;

	heap->datos = datos_nuevos;
	heap->capacidad = tam_nuevo;

	return true;
}
bool heap_encolar(heap_t *heap, void *elem){

	if(heap->cantidad == heap->capacidad){
		size_t tam_nuevo = heap->capacidad*REDIMENSIONADOR;
		if(!_redimensionar_heap(heap,tam_nuevo)){
			return false;
		}
	}

	heap->datos[heap->cantidad] = elem;
	_upheap(heap->datos,heap->cantidad,heap->cmp);
	++heap->cantidad;
	return true;
}
size_t heap_cantidad(const heap_t *heap){

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

	return (heap_cantidad(heap) == 0);
}
void *heap_ver_max(const heap_t *heap){

	if(heap_esta_vacio(heap)) return NULL;

	return(heap->datos[POSICION_DEL_MAX]);
}
void* heap_desencolar(heap_t *heap){

	if(heap_esta_vacio(heap)) return NULL;

	if(heap->cantidad < heap->capacidad/TAMANIO_RELATIVO && CAPACIDAD_INICIAL < heap->capacidad){
		size_t tam_nuevo = heap->capacidad/REDIMENSIONADOR;
		_redimensionar_heap(heap,tam_nuevo);
	}

	void* elem = heap->datos[POSICION_DEL_MAX];

	_swap(heap->datos, POSICION_DEL_MAX, heap->cantidad-1);
	heap->datos[heap->cantidad-1] = NULL;
	--heap->cantidad;
	_downheap(heap->datos,heap->cantidad,POSICION_DEL_MAX,heap->cmp);
	
	return elem;
}
void heap_destruir(heap_t *heap, void destruir_elemento(void *e)){

	if(destruir_elemento){
		for(size_t i = 0; i < heap->cantidad; i++){
			destruir_elemento(heap->datos[i]);
		}
	}

	free(heap->datos);
    free(heap);
}
void heapify(void* elementos[], size_t cant, cmp_func_t cmp){

	size_t ult_padre = (cant/2)-1;

	for(size_t i = ult_padre; i > 0; i--){
		_downheap(elementos, cant, i, cmp);
	}
}
void heap_sort(void *elementos[], size_t cant, cmp_func_t cmp){

	heapify(elementos, cant, cmp);

	for(size_t i = cant; i > 0; i--){
		_downheap(elementos, i, 0, cmp);
		_swap(elementos, 0, i-1);
	}
}