Implementación de Heap

¿Qué es un Heap?

Un heap (montículo) es un árbol binario casi completo donde cada padre es mayor (max-heap) o menor (min-heap) que sus hijos.

Analogía: Imagina una pirámide donde el jefe más importante está arriba, y cada empleado está arriba de los menos importantes que él. El CEO (raíz) es siempre el más importante.

Max-heap

        50
       /  \
     30    40
    / \   /
   10 20 15

Cada padre ≥ sus hijos. La raíz es el máximo.

Min-heap

        5
       / \
     10   8
    / \  /
   15 20 12

Cada padre ≤ sus hijos. La raíz es el mínimo.

¿Por qué usar un Heap?

El heap es perfecto cuando necesitas acceder repetidamente al mayor o menor elemento.

Representación con arreglo

Un heap se almacena en un arreglo (no necesitas punteros):

Índice:  0   1   2   3   4   5
Valor:  50  30  40  10  20  15

Para un nodo en el índice i:

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

Implementación manual (max-heap)

class MaxHeap {
    vector<int> heap;

    void subirNodo(int i) {
        while (i > 0) {
            int padre = (i - 1) / 2;
            if (heap[i] > heap[padre]) {
                swap(heap[i], heap[padre]);
                i = padre;
            } else break;
        }
    }

    void bajarNodo(int i) {
        int n = heap.size();
        while (true) {
            int mayor = i;
            int izq = 2 * i + 1;
            int der = 2 * i + 2;

            if (izq < n && heap[izq] > heap[mayor]) mayor = izq;
            if (der < n && heap[der] > heap[mayor]) mayor = der;

            if (mayor != i) {
                swap(heap[i], heap[mayor]);
                i = mayor;
            } else break;
        }
    }

public:
    void insertar(int val) {
        heap.push_back(val);
        subirNodo(heap.size() - 1);
    }

    int maximo() {
        return heap[0];
    }

    void eliminarMaximo() {
        heap[0] = heap.back();
        heap.pop_back();
        if (!heap.empty()) bajarNodo(0);
    }

    int tamano() { return heap.size(); }
    bool vacio() { return heap.empty(); }
};

Insertar: "subir"

1. Agrega el elemento al final del arreglo.
2. Compara con su padre. Si es mayor, intercámbialos.
3. Repite hasta que esté en su lugar.

Eliminar máximo: "bajar"

1. Reemplaza la raíz con el último elemento.
2. Compara con sus hijos. Intercambia con el mayor.
3. Repite hasta que esté en su lugar.

En la práctica: priority_queue

C++ tiene priority_queue que es un max-heap:

#include <queue>
using namespace std;

// Max-heap (default)
priority_queue<int> maxPQ;
maxPQ.push(10);
maxPQ.push(30);
maxPQ.push(20);
cout << maxPQ.top() << endl;  // 30
maxPQ.pop();  // Elimina el 30

// Min-heap
priority_queue<int, vector<int>, greater<int>> minPQ;
minPQ.push(10);
minPQ.push(30);
minPQ.push(20);
cout << minPQ.top() << endl;  // 10

Heapsort

Ordena un arreglo construyendo un heap y extrayendo el máximo repetidamente. Complejidad: $O(n \log n)$.

void heapify(vector<int> &v, int n, int i) {
    int mayor = i;
    int izq = 2 * i + 1, der = 2 * i + 2;

    if (izq < n && v[izq] > v[mayor]) mayor = izq;
    if (der < n && v[der] > v[mayor]) mayor = der;

    if (mayor != i) {
        swap(v[i], v[mayor]);
        heapify(v, n, mayor);
    }
}

void heapSort(vector<int> &v) {
    int n = v.size();

    // Construir max-heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(v, n, i);
    }

    // Extraer uno por uno
    for (int i = n - 1; i > 0; i--) {
        swap(v[0], v[i]);
        heapify(v, i, 0);
    }
}

Aplicaciones en competencias

K elementos más grandes

// Los K más grandes de un arreglo
priority_queue<int, vector<int>, greater<int>> minPQ;  // min-heap de tamaño K

for (int x : v) {
    minPQ.push(x);
    if (minPQ.size() > k) minPQ.pop();
}
// El min-heap contiene los K más grandes

Mediana dinámica

Mantén dos heaps: un max-heap para la mitad inferior y un min-heap para la superior.

Ejercicio de práctica

Implementa un sistema que soporte:

1. Insertar un número
2. Obtener el mínimo actual
3. Eliminar el mínimo

#include <iostream>
#include <queue>
using namespace std;

int main() {
    int q;
    cin >> q;

    priority_queue<int, vector<int>, greater<int>> minPQ;

    while (q--) {
        int op;
        cin >> op;

        if (op == 1) {
            int x;
            cin >> x;
            minPQ.push(x);
        } else if (op == 2) {
            cout << minPQ.top() << endl;
        } else {
            minPQ.pop();
        }
    }

    return 0;
}