Introducción a los Montículos

Un montículo (heap) es una estructura de datos basada en árboles que satisface la propiedad de orden. En C++, la biblioteca estándar proporciona esta funcionalidad a través del contenedor std::priority_queue, el cual, por defecto, se comporta como un montículo de máximo (max-heap). Esto permite acceder al elemento más grande en tiempo constante O(1) y realizar inserciones o eliminaciones en tiempo logarítmico O(log n).

Búsqueda del K-ésimo Elemento Mayor

Para identificar el elemento que ocupa la posición K en orden descendente, podemos insertar todos los valores en un montículo y extraer los primeros K-1 elementos.

class BuscadorK {
public:
    int obtenerK_esimoMayor(vector<int>& datos, int k) {
        priority_queue<int> monticuloMax;
        
        for (int valor : datos) {
            monticuloMax.push(valor);
        }
        
        while (--k > 0) {
            monticuloMax.pop();
        }
        
        return monticuloMax.top();
    }
};

Elementos más Frecuentes (Top K)

Cuando necesitamos encontrar los K elementos que más se repiten, combinamos un mapa de frecuencias con un montículo. El montículo almacenará pares de datos (frecuencia, valor) para facilitar la ordenación automática basada en las repeticiones.

class AnalizadorFrecuencia {
public:
    vector<int> obtenerTopK(vector<int>& nums, int k) {
        unordered_map<int, int> contador;
        for (int n : nums) {
            contador[n]++;
        }

        priority_queue<pair<int, int>> ranking;
        for (auto const& [valor, frec] : contador) {
            ranking.push({frec, valor});
        }

        vector<int> resultado;
        while (k-- > 0 && !ranking.empty()) {
            resultado.push_back(ranking.top().second);
            ranking.pop();
        }
        return resultado;
    }
};

Personalización del Orden en Priority Queues

Para invertir el comportamiento predeterminado y crear un montículo de mínimo (min-heap), o aplicar una lógica personalizada, se puede utilizar un comparador de tipo functor.

#include <iostream>
#include <queue>
#include <vector>

struct OrdenAscendente {
    bool operator()(int a, int b) {
        return a > b; // El valor menor tendrá mayor prioridad
    }
};

int main() {
    std::priority_queue<int, std::vector<int>, OrdenAscendente> minHeap;

    minHeap.push(15);
    minHeap.push(3);
    minHeap.push(9);

    while (!minHeap.empty()) {
        std::cout << minHeap.top() << " "; // Salida: 3 9 15
        minHeap.pop();
    }
    return 0;
}

Gestión Dinámica de la Mediana

Un problema clásico es calcular la mediana de un flujo constante de números. El enfoque más eficiente consiste en mantener dos montículos equilibrados:

• Un montículo de máximo para la mitad inferior de los datos.
• Un montículo de mínimo para la mitad superior de los datos.

class GestorMediana {
private:
    priority_queue<int> maxHeap; // Mitad pequeña
    priority_queue<int, vector<int>, greater<int>> minHeap; // Mitad grande

public:
    void agregarNumero(int num) {
        if (maxHeap.empty() || num <= maxHeap.top()) {
            maxHeap.push(num);
        } else {
            minHeap.push(num);
        }

        // Balancear tamaños: maxHeap puede tener como máximo uno más que minHeap
        if (maxHeap.size() > minHeap.size() + 1) {
            minHeap.push(maxHeap.top());
            maxHeap.pop();
        } else if (minHeap.size() > maxHeap.size()) {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }

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