/*
 * heap.h - Implementación básica de Heap (Montículo)
 *
 * Inspirado en "Data Structures and Algorithms Made Easy"
 * por Narasimha Karumanchi.
 *
 * Define un TAD de heap (min-heap y max-heap) con
 * operaciones fundamentales para colas de prioridad
 * y algoritmos de ordenamiento.
 */

#ifndef HEAP_H
#define HEAP_H

#include <stdbool.h>

/* Tamaño máximo del heap */
#define MAX_HEAP 100

/* ===== ESTRUCTURA ===== */

/* Estructura del heap */
typedef struct heap {
  int datos[MAX_HEAP];
  int tamano;        /* Número de elementos actuales */
  int tipo;          /* 0 = min-heap, 1 = max-heap */
} heap_t;

/* ===== CREACIÓN ===== */

/* Crea un nuevo heap vacío del tipo especificado.
 * tipo: 0 para min-heap, 1 para max-heap.
 * Retorna NULL si no se puede asignar memoria. */
heap_t *heap_crear(int tipo);

/* ===== INSERCIÓN ===== */

/* Inserta un elemento en el heap manteniendo la propiedad de heap.
 * Retorna 1 si se insertó correctamente, 0 si el heap está lleno. */
int heap_insertar(heap_t *heap, int elemento);

/* ===== ELIMINACIÓN ===== */

/* Extrae y retorna el elemento mínimo del min-heap.
 * Retorna -1 si el heap está vacío.
 * Pre: heap->tipo == 0 (min-heap) */
int heap_extraer_min(heap_t *heap);

/* Extrae y retorna el elemento máximo del max-heap.
 * Retorna -1 si el heap está vacío.
 * Pre: heap->tipo == 1 (max-heap) */
int heap_extraer_max(heap_t *heap);

/* ===== CONSULTA ===== */

/* Retorna el elemento mínimo sin extraerlo.
 * Retorna -1 si el heap está vacío.
 * Pre: heap->tipo == 0 (min-heap) */
int heap_minimo(heap_t *heap);

/* Retorna el elemento máximo sin extraerlo.
 * Retorna -1 si el heap está vacío.
 * Pre: heap->tipo == 1 (max-heap) */
int heap_maximo(heap_t *heap);

/* Verifica si el heap está vacío */
bool heap_vacio(heap_t *heap);

/* ===== TAMAÑO ===== */

/* Devuelve el número de elementos en el heap */
int heap_tamano(heap_t *heap);

/* ===== OPERACIONES INTERNAS ===== */

/* Restaura la propiedad de heap desde un nodo hacia arriba.
 * Se usa después de insertar un elemento. */
void heapify_up(heap_t *heap, int indice);

/* Restaura la propiedad de heap desde un nodo hacia abajo.
 * Se usa después de extraer un elemento. */
void heapify_down(heap_t *heap, int indice);

/* Intercambia dos elementos en el heap */
void heap_intercambiar(heap_t *heap, int i, int j);

/* ===== CONSTRUCCIÓN ===== */

/* Construye un heap desde un array de n elementos.
 * Retorna 1 si se construyó correctamente, 0 en caso contrario. */
int heap_construir(heap_t *heap, int *array, int n);

/* ===== ORDENAMIENTO ===== */

/* Ordena un array usando heapsort.
 * Modifica el array original. */
void heapsort(int *array, int n);

/* ===== DESTRUCCIÓN ===== */

/* Libera toda la memoria del heap */
void heap_destruir(heap_t *heap);

/* ===== IMPRESIÓN ===== */

/* Imprime los elementos del heap (para debugging) */
void heap_imprimir(heap_t *heap);

#endif // HEAP_H