Implementación de Heap

¿Qué es un Heap?

Un heap (montículo) es un árbol binario completo que satisface la propiedad de heap:

• Max-Heap: Cada padre es mayor o igual que sus hijos
• Min-Heap: Cada padre es menor o igual que sus hijos

Max-Heap:          Min-Heap:
      90                 10
     /  \               /  \
   80    70           20    30
  / \   /            / \   /
 50 60 65           40 50 35

¿Para qué sirve?

Ideal para:

• Encontrar el k-ésimo elemento más grande/pequeño
• Ordenamiento (HeapSort)
• Algoritmos de Dijkstra y Prim
• Merge de k listas ordenadas

Representación en array

Almacenamos el heap en un array usando estas fórmulas (indexando desde 1):

Array:    [_, 90, 80, 70, 50, 60, 65]
Índices:      1   2   3   4   5   6

        90 (índice 1)
       /  \
     80    70  (índices 2, 3)
    / \    /
   50 60  65   (índices 4, 5, 6)

int padre(int i) { return i / 2; }
int hijoIzq(int i) { return 2 * i; }
int hijoDer(int i) { return 2 * i + 1; }

Implementación de Max-Heap

class MaxHeap {
private:
    vector<int> heap;
    int tam;

    void subir(int i) {
        while (i > 1 && heap[padre(i)] < heap[i]) {
            swap(heap[padre(i)], heap[i]);
            i = padre(i);
        }
    }

    void bajar(int i) {
        while (true) {
            int mayor = i;
            int izq = hijoIzq(i);
            int der = hijoDer(i);

            if (izq <= tam && heap[izq] > heap[mayor]) {
                mayor = izq;
            }
            if (der <= tam && heap[der] > heap[mayor]) {
                mayor = der;
            }

            if (mayor == i) break;

            swap(heap[i], heap[mayor]);
            i = mayor;
        }
    }

    int padre(int i) { return i / 2; }
    int hijoIzq(int i) { return 2 * i; }
    int hijoDer(int i) { return 2 * i + 1; }

public:
    MaxHeap() {
        heap.push_back(0);  // Índice 0 no se usa
        tam = 0;
    }

    void insertar(int valor) {
        heap.push_back(valor);
        tam++;
        subir(tam);
    }

    int obtenerMax() {
        if (tam == 0) throw runtime_error("Heap vacío");
        return heap[1];
    }

    int extraerMax() {
        if (tam == 0) throw runtime_error("Heap vacío");

        int maximo = heap[1];
        heap[1] = heap[tam];
        heap.pop_back();
        tam--;

        if (tam > 0) {
            bajar(1);
        }

        return maximo;
    }

    bool vacio() { return tam == 0; }
    int size() { return tam; }
};

Uso

int main() {
    MaxHeap heap;

    heap.insertar(50);
    heap.insertar(30);
    heap.insertar(70);
    heap.insertar(10);
    heap.insertar(90);

    cout << "Máximo: " << heap.obtenerMax() << endl;  // 90

    while (!heap.vacio()) {
        cout << heap.extraerMax() << " ";  // 90 70 50 30 10
    }
    cout << endl;

    return 0;
}

Visualización de operaciones

Insertar

Heap inicial:     Insertar 85:        Subir (heapify up):
      90                90                  90
     /  \              /  \                /  \
   80    70    →     80    70      →     85    70
  / \               / \   /             / \   /
 50 60            50 60 85            50 60 80

1. Agregar al final
2. Subir mientras sea mayor que su padre

Extraer máximo

Heap inicial:     Mover último a raíz:   Bajar (heapify down):
      90                65                   80
     /  \              /  \                 /  \
   80    70    →     80    70      →      65    70
  / \   /           / \                  / \
 50 60 65          50 60                50 60

1. Guardar raíz (máximo)
2. Mover último elemento a raíz
3. Bajar mientras sea menor que algún hijo

Min-Heap

Simplemente invertimos las comparaciones:

class MinHeap {
private:
    vector<int> heap;
    int tam;

    void subir(int i) {
        while (i > 1 && heap[padre(i)] > heap[i]) {  // Cambio: > en vez de <
            swap(heap[padre(i)], heap[i]);
            i = padre(i);
        }
    }

    void bajar(int i) {
        while (true) {
            int menor = i;  // Cambio: buscamos menor
            int izq = hijoIzq(i);
            int der = hijoDer(i);

            if (izq <= tam && heap[izq] < heap[menor]) {  // Cambio: <
                menor = izq;
            }
            if (der <= tam && heap[der] < heap[menor]) {  // Cambio: <
                menor = der;
            }

            if (menor == i) break;

            swap(heap[i], heap[menor]);
            i = menor;
        }
    }

    // ... resto igual
};

Usando priority_queue de STL

En competencias, usa priority_queue:

#include <queue>

int main() {
    // Max-heap (por defecto)
    priority_queue<int> maxHeap;

    maxHeap.push(50);
    maxHeap.push(30);
    maxHeap.push(70);

    cout << maxHeap.top() << endl;  // 70
    maxHeap.pop();
    cout << maxHeap.top() << endl;  // 50

    // Min-heap
    priority_queue<int, vector<int>, greater<int>> minHeap;

    minHeap.push(50);
    minHeap.push(30);
    minHeap.push(70);

    cout << minHeap.top() << endl;  // 30

    return 0;
}

Con pares

// Ordenar por primer elemento (menor primero), luego por segundo
priority_queue<
    pair<int, int>,
    vector<pair<int, int>>,
    greater<pair<int, int>>
> pq;

pq.push({3, 100});
pq.push({1, 200});
pq.push({2, 300});

while (!pq.empty()) {
    auto [a, b] = pq.top();
    pq.pop();
    cout << a << " " << b << endl;
}
// Salida: 1 200, 2 300, 3 100

Con estructuras personalizadas

struct Tarea {
    int prioridad;
    string nombre;
};

// Comparador: mayor prioridad primero
struct Comparador {
    bool operator()(const Tarea& a, const Tarea& b) {
        return a.prioridad < b.prioridad;  // < para max-heap
    }
};

priority_queue<Tarea, vector<Tarea>, Comparador> pq;

pq.push({3, "Baja"});
pq.push({10, "Alta"});
pq.push({5, "Media"});

while (!pq.empty()) {
    cout << pq.top().nombre << " (" << pq.top().prioridad << ")" << endl;
    pq.pop();
}
// Alta (10), Media (5), Baja (3)

Construir heap en O(n)

En lugar de n inserciones O(log n), podemos construir en O(n):

void construirHeap(vector<int>& arr) {
    int n = arr.size();
    // Empezar desde el último nodo no-hoja
    for (int i = n / 2; i >= 1; i--) {
        bajar(arr, i, n);
    }
}

void bajar(vector<int>& arr, int i, int n) {
    while (true) {
        int mayor = i;
        int izq = 2 * i;
        int der = 2 * i + 1;

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

        if (mayor == i) break;
        swap(arr[i], arr[mayor]);
        i = mayor;
    }
}

HeapSort

Ordenar usando heap en O(n log n):

void heapSort(vector<int>& arr) {
    int n = arr.size() - 1;  // Ignoramos índice 0

    // Construir max-heap
    for (int i = n / 2; i >= 1; i--) {
        bajar(arr, i, n);
    }

    // Extraer elementos uno por uno
    for (int i = n; i > 1; i--) {
        swap(arr[1], arr[i]);  // Mover máximo al final
        bajar(arr, 1, i - 1);  // Restaurar heap
    }
}

Problemas clásicos

K elementos más grandes

vector<int> kMasGrandes(vector<int>& nums, int k) {
    // Min-heap de tamaño k
    priority_queue<int, vector<int>, greater<int>> pq;

    for (int num : nums) {
        pq.push(num);
        if (pq.size() > k) {
            pq.pop();  // Eliminar el menor
        }
    }

    vector<int> resultado;
    while (!pq.empty()) {
        resultado.push_back(pq.top());
        pq.pop();
    }
    return resultado;
}

Mediana en stream

class MedianFinder {
    priority_queue<int> maxHeap;  // Mitad menor
    priority_queue<int, vector<int>, greater<int>> minHeap;  // Mitad mayor

public:
    void agregar(int num) {
        maxHeap.push(num);
        minHeap.push(maxHeap.top());
        maxHeap.pop();

        if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }

    double mediana() {
        if (maxHeap.size() > minHeap.size()) {
            return maxHeap.top();
        }
        return (maxHeap.top() + minHeap.top()) / 2.0;
    }
};

Merge k listas ordenadas

ListNode* mergeKListas(vector<ListNode*>& listas) {
    auto cmp = [](ListNode* a, ListNode* b) {
        return a->val > b->val;  // Min-heap
    };
    priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);

    for (auto lista : listas) {
        if (lista) pq.push(lista);
    }

    ListNode dummy(0);
    ListNode* actual = &dummy;

    while (!pq.empty()) {
        ListNode* nodo = pq.top();
        pq.pop();

        actual->next = nodo;
        actual = actual->next;

        if (nodo->next) {
            pq.push(nodo->next);
        }
    }

    return dummy.next;
}

Template para competencias

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Max-heap
    priority_queue<int> maxPQ;

    // Min-heap
    priority_queue<int, vector<int>, greater<int>> minPQ;

    // Con pares (ordenar por distancia, luego por nodo)
    priority_queue<
        pair<int, int>,
        vector<pair<int, int>>,
        greater<pair<int, int>>
    > dijkstraPQ;

    // Operaciones comunes
    // pq.push(x);     // Insertar
    // pq.top();       // Ver tope
    // pq.pop();       // Eliminar tope
    // pq.empty();     // ¿Está vacío?
    // pq.size();      // Tamaño

    return 0;
}

Resumen

Ejercicios recomendados

1. LeetCode - Kth Largest Element
2. LeetCode - Find Median from Data Stream
3. LeetCode - Merge k Sorted Lists
4. CSES - Traffic Lights
5. Codeforces - Deque Summations