Min-heap en C: ejercicio resuelto

Si buscas min-heap en C ejercicio resuelto, aquí tienes la implementación completa con array: inserción O(log n), extracción del mínimo O(log n) y la operación de heapify que mantiene la propiedad de heap.

Un min-heap es un árbol binario completo donde cada nodo es menor o igual que sus hijos. Se representa eficientemente con un array: el hijo izquierdo del nodo i está en 2*i+1, el derecho en 2*i+2 y el padre en (i-1)/2.

Enunciado

Implementa un min-heap con capacidad fija que soporte:

insertar(heap, valor): inserta un elemento y restaura la propiedad.
extraer_min(heap): elimina y devuelve el elemento mínimo.
imprimir(heap): muestra el array interno.

Inserta los valores {5, 3, 8, 1, 4, 2} y extrae el mínimo tres veces.

Solución en C

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <stdio.h>
#include <stdlib.h>

#define MAX_HEAP 64

typedef struct {
    int datos[MAX_HEAP];
    int tamaño;
} MinHeap;

static void intercambiar(int *a, int *b) { int t = *a; *a = *b; *b = t; }

/* Sube el nodo i hasta su posición correcta */
static void subir(MinHeap *h, int i) {
    while (i > 0) {
        int padre = (i - 1) / 2;
        if (h->datos[padre] <= h->datos[i]) break;
        intercambiar(&h->datos[padre], &h->datos[i]);
        i = padre;
    }
}

/* Baja el nodo i hasta su posición correcta */
static void bajar(MinHeap *h, int i) {
    while (1) {
        int menor = i;
        int izq = 2 * i + 1, der = 2 * i + 2;
        if (izq < h->tamaño && h->datos[izq] < h->datos[menor]) menor = izq;
        if (der < h->tamaño && h->datos[der] < h->datos[menor]) menor = der;
        if (menor == i) break;
        intercambiar(&h->datos[i], &h->datos[menor]);
        i = menor;
    }
}

void insertar(MinHeap *h, int val) {
    if (h->tamaño >= MAX_HEAP) { fprintf(stderr, "Heap lleno\n"); return; }
    h->datos[h->tamaño++] = val;
    subir(h, h->tamaño - 1);
}

int extraer_min(MinHeap *h) {
    if (h->tamaño == 0) { fprintf(stderr, "Heap vacío\n"); return -1; }
    int min = h->datos[0];
    h->datos[0] = h->datos[--h->tamaño];
    bajar(h, 0);
    return min;
}

void imprimir(const MinHeap *h) {
    printf("Heap [%d]: ", h->tamaño);
    for (int i = 0; i < h->tamaño; i++) printf("%d ", h->datos[i]);
    printf("\n");
}

int main(void) {
    MinHeap h = {.tamaño = 0};
    int vals[] = {5, 3, 8, 1, 4, 2};

    for (int i = 0; i < 6; i++) {
        insertar(&h, vals[i]);
        imprimir(&h);
    }

    printf("\nExtrayendo mínimos:\n");
    for (int i = 0; i < 3; i++)
        printf("  extraer_min() = %d\n", extraer_min(&h));

    printf("\nHeap final: "); imprimir(&h);
    return 0;
}

Resultado esperado

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
Heap [1]: 5 
Heap [2]: 3 5 
Heap [3]: 3 5 8 
Heap [4]: 1 3 8 5 
Heap [5]: 1 3 8 5 4 
Heap [6]: 1 3 2 5 4 8 

Extrayendo mínimos:
  extraer_min() = 1
  extraer_min() = 2
  extraer_min() = 3

Heap final: Heap [3]: 4 5 8 

Errores frecuentes

Calcular mal los índices de hijos y padre: hijo izquierdo = 2*i+1, hijo derecho = 2*i+2, padre = (i-1)/2. Con indexación en 1 las fórmulas son distintas.
No decrementar tamaño antes de llamar a bajar en extraer_min: si tamaño no se reduce, el último elemento que se colocó en la raíz se compara consigo mismo.
Confundir min-heap con max-heap: en min-heap el padre es menor que los hijos; en max-heap es al revés. Solo cambia el signo de la comparación.
No validar que el heap no esté vacío antes de extraer_min: acceder a datos[0] con tamaño == 0 es comportamiento indefinido.

Aplicación práctica

El min-heap es la estructura subyacente de las colas de prioridad, usadas en el algoritmo de Dijkstra, en la codificación de Huffman, en la planificación de tareas por prioridad y en el algoritmo de ordenación heapsort.

Siguiente ejercicio recomendado

Práctica guiada y libro completo

Si quieres una ruta completa con progresión real de dificultad:

FAQ

¿Por qué se usa un array y no un árbol con punteros para el heap?

Porque el árbol binario completo se mapea perfectamente a un array sin necesidad de punteros: los índices de padre e hijos se calculan aritméticamente. Esto reduce el consumo de memoria, mejora la localidad de caché y simplifica el código.

¿Qué es la operación de heapify (o build-heap)?

Convierte un array arbitrario en un heap válido en O(n) aplicando bajar a todos los nodos internos de abajo a arriba (desde n/2 - 1 hasta 0). Es más eficiente que insertar los n elementos uno a uno (que costaría O(n log n)).

¿Cómo convertir un min-heap en max-heap?

Solo hay que invertir las comparaciones: en subir, cambiar <= por >=; en bajar, cambiar < por >. El resto del código permanece idéntico.