Estructuras de datos - Montón

Un montón (Heap) es una estructura especial de árbol binario completo que satisface la propiedad de orden de montón. El montón solo garantiza la relación de tamaño entre nodos padre e hijo, no exige un orden estricto entre los subárboles izquierdo y derecho.


Definición y almacenamiento del montón

Montón (Heap) — Estructura de montón máximo y almacenamiento en array

Vista de árbol (montón máximo)

15Índice 0
10Índice 1
8Índice 2
53
34
25

Vista de array (almacenamiento compacto)

15
[0]
10
[1]
8
[2]
5
[3]
3
[4]
2
[5]

Padre: (i-1)/2 | Hijo izquierdo: 2i+1 | Hijo derecho: 2i+2

Árbol binario completo → Naturalmente apto para arrays, sin sobrecarga de punteros

Flotar (Sift Up) (inserción) O(log n)

Colocar el nuevo elemento al final → comparar con el padre → si es mayor, intercambiar → repetir hasta la cima del montón

Hundir (Sift Down) (eliminación de la cima) O(log n)

Mover el último elemento a la cima → comparar con el hijo mayor → si es menor, intercambiar → repetir hasta una hoja

Dos tipos de montón:

  • Montón máximo (Max Heap): cada nodo padre ≥ nodo hijo, el nodo raíz es el valor máximo
  • Montón mínimo (Min Heap): cada nodo padre ≤ nodo hijo, el nodo raíz es el valor mínimo

Dado que el montón es un árbol binario completo, es naturalmente adecuado para almacenarse con un array:

Nodo (índice i)RelaciónPosición (basada en 0)
Nodo padreparent(i)(i - 1) / 2
Hijo izquierdoleft(i)2 * i + 1
Hijo derechoright(i)2 * i + 2

Inserción y eliminación en el montón (proceso de heapify)

Ejemplo

#include <stdio.h>

#define MAX 100

/* Estructura de montón máximo */
struct MaxHeap {
    int arr[MAX];
    int size;  /* Número actual de elementos */
};

void initHeap(struct MaxHeap* h) { h->size = 0; }

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

/* Flotar (Sift Up): ajustar el nuevo elemento insertado de abajo hacia arriba
comparar con el nodo padre, si es mayor que el padre, intercambiar, hasta que se cumpla el orden del montón */

void siftUp(struct MaxHeap* h, int idx) {
    while (idx > 0) {
        int parent = (idx - 1) / 2;
        if (h->arr[idx] <= h->arr[parent]) break;
        swap(&h->arr[idx], &h->arr[parent]);
        idx = parent;
    }
}

/* Inserción: primero colocar el elemento al final, luego ajustar con Sift Up O(log n) */
void insert(struct MaxHeap* h, int value) {
    if (h->size >= MAX) return;
    h->arr[h->size] = value;
    siftUp(h, h->size);
    h->size++;
}

/* Hundir (Sift Down): ajustar desde la raíz hacia abajo
comparar con el hijo mayor, si es menor, intercambiar, hasta que se cumpla el orden del montón */

void siftDown(struct MaxHeap* h, int idx) {
    while (1) {
        int largest = idx;
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;

        if (left < h->size && h->arr[left] > h->arr[largest])
            largest = left;
        if (right < h->size && h->arr[right] > h->arr[largest])
            largest = right;

        if (largest == idx) break;
        swap(&h->arr[idx], &h->arr[largest]);
        idx = largest;
    }
}

/* Eliminar la cima (valor máximo): mover el último elemento a la cima, luego ajustar con Sift Down O(log n) */
int extractMax(struct MaxHeap* h) {
    if (h->size == 0) return -1;
    int maxVal = h->arr[0];
    h->arr[0] = h->arr[--h->size];  /* Mover el último elemento a la cima */
    siftDown(h, 0);                 /* Ajuste con Sift Down */
    return maxVal;
}

int main() {
    struct MaxHeap h;
    initHeap(&h);

    int vals[] = {3, 10, 5, 8, 2, 15};
    for (int i = 0; i < 6; i++) insert(&h, vals[i]);

    printf("Sacar los valores máximos en orden: ");
    while (h.size > 0) {
        printf("%d ", extractMax(&h));
    }
    printf("\n");  /* Salida: 15 10 8 5 3 2 (orden descendente) */
    return 0;
}

Escenarios de aplicación

EscenarioDescripción
Cola de prioridadEl montón es la implementación subyacente más común de la cola de prioridad
HeapsortAlgoritmo de ordenamiento en el lugar O(n log n) (se explica en el Capítulo 18)
Problema de Top KUsar un montón mínimo para mantener los K elementos más grandes
Otras extensiones