What is a Heap?

Un heap (o montículo) es una estructura de datos en forma de árbol que cumple con un invariante simple: cada padre es menor que (o igual a) sus hijos. El valor más pequeño siempre se encuentra en la raíz, listo para ser leído en O(1). Esta variante específica se llama min-heap; la imagen especular con el invariante del valor más grande en la raíz es un max-heap.

La parte ingeniosa es el almacenamiento. Aunque lo visualizamos como un árbol, un heap reside en un array plano. Para el nodo en el índice i:

• Su padre está en el índice (i - 1) / 2.
• Su hijo izquierdo está en el índice 2 * i + 1.
• Su hijo derecho está en el índice 2 * i + 2.

Sin punteros, sin objetos de nodo: solo matemática de índices. Eso hace que los heaps sean muy amigables con la caché y fáciles de implementar.

Las cinco operaciones principales en un min-heap son:

1. Peek: Retornar el valor más pequeño (la raíz).
2. Insert: Añadir un valor y desplazarlo hacia arriba (bubble up) hasta su lugar.
3. ExtractMin: Eliminar y retornar el valor más pequeño.
4. Size: Retornar cuántos valores hay almacenados.
5. IsEmpty: Comprobar si el heap está vacío.

¡Vamos a crear una clase MinHeap!