¿Cómo funcionan los heaps?

Los heaps, o montículos, son una estructura de datos de tipo árbol especialmente diseñada para garantizar un acceso rápido al elemento ""máximo"" o ""mínimo"" de un conjunto de datos. Estos se clasifican principalmente en dos tipos: max-heaps y min-heaps. En un max-heap, el valor máximo se encuentra en la raíz del árbol y, por lo tanto, se puede acceder en tiempo constante, mientras que en un min-heap, el valor mínimo ocupa la raíz.

La estructura del heap asegura que, para cada nodo \( i \) excepto la raíz, el valor del nodo \( i \) es mayor (en un max-heap) o menor (en un min-heap) que el valor de su nodo padre. Esta propiedad hace que los heaps sean útiles para implementaciones eficientes de colas de prioridad.

El funcionamiento de los heaps se basa en operaciones principales como insertar y extraer el máximo (o mínimo). La inserción se realiza agregando el nuevo elemento al final del árbol (manteniendo la forma completa del árbol) y luego realizando una operación de ""ascenso"" donde el elemento insertado se compara y, si es necesario, se intercambia con su nodo padre hasta que se restablecen las propiedades del heap.

function insert(value, heap) {
    heap.push(value);
    siftUp(heap.length - 1, heap);
}

function siftUp(index, heap) {
    let parentIndex = Math.floor((index - 1) / 2);
    while (index > 0 && heap[parentIndex] < heap[index]) {
        swap(index, parentIndex, heap);
        index = parentIndex;
        parentIndex = Math.floor((index - 1) / 2);
    }
}

La extracción del máximo (o mínimo) se realiza eliminando la raíz del árbol, luego moviendo el último elemento del árbol a la raíz y finalmente realizando una operación de ""descenso"" donde este elemento se compara y se intercambia con sus hijos hasta que se restablecen las propiedades del heap.

function extractMax(heap) {
    const max = heap[0];
    heap[0] = heap.pop();
    siftDown(0, heap);
    return max;
}

function siftDown(index, heap) {
    let leftChildIndex = 2 * index + 1;
    let rightChildIndex = 2 * index + 2;
    let largest = index;

    if (leftChildIndex < heap.length && heap[leftChildIndex] > heap[largest]) {
        largest = leftChildIndex;
    }
    if (rightChildIndex < heap.length && heap[rightChildIndex] > heap[largest]) {
        largest = rightChildIndex;
    }
    if (largest !== index) {
        swap(index, largest, heap);
        siftDown(largest, heap);
    }
}

Gracias a estas operaciones, los heaps son extremadamente útiles en aplicaciones que requieren acceso rápido y repetido a los elementos más grandes o más pequeños, como algoritmos de selección de k-ésimos elementos más grandes, simulación de eventos discretos, y más.