Los heaps son árboles binarios completos que mantienen la propiedad de orden parcial: cada nodo es mayor o igual que sus hijos (max-heap) o menor o igual (min-heap). Gracias a esta propiedad, permiten acceder rápidamente al elemento de mayor o menor prioridad y son la base de las colas de prioridad eficientes.
Se almacenan en arreglos contiguos, lo que evita nodos enlazados y mejora la localidad de caché sin sacrificar la complejidad logarítmica.
Conocer estos términos agiliza la lectura de los algoritmos de heapify e inserción.
El arreglo almacena el heap nivel por nivel. A partir de un índice i se calculan sus vecinos sin punteros adicionales:
(i - 1) / 2 (truncando decimales).2 * i + 1.2 * i + 2.Esta representación es compacta y permite reducir el uso de memoria respecto a las listas enlazadas.
En ambos heaps las operaciones fundamentales son insert y extract. El max-heap sirve de ejemplo porque el min-heap solo requiere invertir las comparaciones.
#define CAP_HEAP 128
typedef struct {
int datos[CAP_HEAP];
int cantidad;
} Heap;
void heap_init(Heap *h) {
h->cantidad = 0;
}
static void sift_up(Heap *h, int idx) {
while (idx > 0) {
int padre = (idx - 1) / 2;
if (h->datos[idx] <= h->datos[padre]) {
break;
}
int tmp = h->datos[idx];
h->datos[idx] = h->datos[padre];
h->datos[padre] = tmp;
idx = padre;
}
}
static void sift_down(Heap *h, int idx) {
while (1) {
int izq = 2 * idx + 1;
int der = izq + 1;
int mayor = idx;
if (izq < h->cantidad && h->datos[izq] > h->datos[mayor]) {
mayor = izq;
}
if (der < h->cantidad && h->datos[der] > h->datos[mayor]) {
mayor = der;
}
if (mayor == idx) {
break;
}
int tmp = h->datos[idx];
h->datos[idx] = h->datos[mayor];
h->datos[mayor] = tmp;
idx = mayor;
}
}
int heap_insert(Heap *h, int valor) {
if (h->cantidad == CAP_HEAP) {
return 0;
}
h->datos[h->cantidad] = valor;
sift_up(h, h->cantidad);
h->cantidad++;
return 1;
}
int heap_extract(Heap *h, int *valor) {
if (h->cantidad == 0) {
return 0;
}
*valor = h->datos[0];
h->cantidad--;
h->datos[0] = h->datos[h->cantidad];
sift_down(h, 0);
return 1;
}Ambas operaciones mantienen la complejidad O(log n). Para un min-heap simplemente se reemplaza la comparación > por <.
Los heaps pueden invertirse con una sola condición de comparación o utilizando un factor signo que se multiplica por cada valor. Elegir uno u otro depende del problema: Dijkstra requiere min-heap, mientras que un planificador que atiende prioridades altas usa max-heap.
En implementaciones genéricas se recibe un puntero a función comparadora para que el usuario decida la relación de orden.
Cuando se parte de un arreglo arbitrario es más eficiente aplicar heapify de abajo hacia arriba que insertar elemento por elemento. El siguiente algoritmo transforma el arreglo en O(n):
void heapify(Heap *h, int *valores, int n) {
if (n > CAP_HEAP) {
n = CAP_HEAP;
}
memcpy(h->datos, valores, n * sizeof(int));
h->cantidad = n;
for (int i = (h->cantidad / 2) - 1; i >= 0; --i) {
sift_down(h, i);
}
}Solo los nodos internos (hasta n/2) requieren reposicionarse porque los nodos hoja ya cumplen la propiedad del heap.
Heapsort construye un heap max y luego extrae repetidamente para generar una secuencia ordenada de mayor a menor o viceversa. Su complejidad es O(n log n) y no necesita memoria auxiliar:
heapify al arreglo.cantidad y ejecutar sift_down.El algoritmo es in-situ; solo intercambia elementos dentro del mismo arreglo.
El siguiente programa crea un max-heap, inserta valores, extrae todos y luego demuestra cómo heapify acelera la construcción:
#include <stdio.h>
#include <string.h>
#define CAP_HEAP 64
typedef struct {
int datos[CAP_HEAP];
int cantidad;
} Heap;
void heap_init(Heap *h) {
h->cantidad = 0;
}
static void sift_up(Heap *h, int idx) {
while (idx > 0) {
int padre = (idx - 1) / 2;
if (h->datos[idx] <= h->datos[padre]) {
break;
}
int tmp = h->datos[idx];
h->datos[idx] = h->datos[padre];
h->datos[padre] = tmp;
idx = padre;
}
}
static void sift_down(Heap *h, int idx) {
while (1) {
int izq = 2 * idx + 1;
int der = izq + 1;
int mayor = idx;
if (izq < h->cantidad && h->datos[izq] > h->datos[mayor]) {
mayor = izq;
}
if (der < h->cantidad && h->datos[der] > h->datos[mayor]) {
mayor = der;
}
if (mayor == idx) {
break;
}
int tmp = h->datos[idx];
h->datos[idx] = h->datos[mayor];
h->datos[mayor] = tmp;
idx = mayor;
}
}
int heap_insert(Heap *h, int valor) {
if (h->cantidad == CAP_HEAP) {
return 0;
}
h->datos[h->cantidad] = valor;
sift_up(h, h->cantidad);
h->cantidad++;
return 1;
}
int heap_extract(Heap *h, int *valor) {
if (h->cantidad == 0) {
return 0;
}
*valor = h->datos[0];
h->cantidad--;
h->datos[0] = h->datos[h->cantidad];
sift_down(h, 0);
return 1;
}
void heapify(Heap *h, const int *valores, int n) {
if (n > CAP_HEAP) {
n = CAP_HEAP;
}
memcpy(h->datos, valores, n * sizeof(int));
h->cantidad = n;
for (int i = (h->cantidad / 2) - 1; i >= 0; --i) {
sift_down(h, i);
}
}
void imprimir(const Heap *h) {
printf("[heap] n=%d -> ", h->cantidad);
for (int i = 0; i < h->cantidad; ++i) {
printf("%d ", h->datos[i]);
}
puts("");
}
int main(void) {
Heap heap;
heap_init(&heap);
heap_insert(&heap, 45);
heap_insert(&heap, 10);
heap_insert(&heap, 78);
heap_insert(&heap, 32);
imprimir(&heap);
int valor;
while (heap_extract(&heap, &valor)) {
printf("extraido: %d\n", valor);
}
imprimir(&heap);
int datos[] = {5, 1, 9, 4, 2, 7};
heapify(&heap, datos, sizeof datos / sizeof datos[0]);
imprimir(&heap);
return 0;
}Integra las versiones completas de inserción, extracción y heapify para ejecutar el ejemplo. Observa cómo los valores se devuelven en orden descendente a pesar de haberse cargado en desorden.