Heaps o Montículos

Si tienes una carrera formal en computación, o alguna rama relacionada, probablemente habrás visto alguna clase de estructura de datos y recordarás los Heaps o -montículos en español- En caso de que no recuerdes, o no sabías que existían, en este post intentaré explicar de manera resumida esta interesante estructura de datos.

Las operaciones en los heaps son eficientes, la mayoría son O(logn). Los montículos se usan principalmente en el algoritmo Heapsort y en las Priority Queues (Colas de prioridades). Está representada por una estructura de tipo árbol y su característica principal es que el nodo padre -o raíz- siempre es mayor, o menor según sea el caso, que sus nodos hijos.

Los Heaps pueden ser MaxHeaps (El nodo padre es mayor que los hijos) o MinHeaps (El nodo padre siempre es menor que los hijos). La representación más usada son los Binary Heaps (montículos binarios) que tienen la estructura de un árbol binario. La forma más usada para almacenar los datos en esta estructura es un Array (dinámico por lo general), esto genera un árbol binario completo (todas las secciones deben estar balanceadas, con una posible excepción de la última) por lo que sabemos de antemano su forma y con simple aritmética podemos calcular los índices en el array de los nodos hijos a partir del padre y viceversa.

La imagen representa un MaxHeap, nótese como los nodos padres o raíz siempre son mayores a los hijos, y cada vez que se inserte un nuevo nodo o se elimine el nodo raíz se debe garantizar esta propiedad.

Las operaciones básicas (No necesariamente con estos nombres) de un Heap son:

• Add(item) Inserta un ítem en el montículo y lo reordena.
• GetTop() – Regresa el ítem del tope (El mayor o menor).
• RemoveTop() – Elimina un ítem del tope (El mayor o menor según sea el caso) y lo retorna.
• Heapify(array, from)  - Mantiene la propiedad del montículo (Mayor o menor item en el tope).
• Left(rootIndex) – Calcula el índice del hijo izquierdo a partir del índice del padre 
• (rootIndex * 2) + 1
• Right(rootIndex) – Calcula el índice del hijo derecho a partir del índice del padre 
• (rootIndex * 2) + 2
• Root(rootIndex) – Calcula el índice del padre a partir del hijo (izquierdo o derecho) 
• (rootIndex – 1) / 2

Las últimas 3 fórmulas son para arrays con índices base 0, recalco esto porque en algunos libros usan arrays con índice base 1 y la fórmula es ligeramente distinta. Trataré de explicar las operaciones Add y Remove que son las principales (pero al final dejo una implementación que hice en C# donde están las demás operaciones con comentarios):

Add(item) – Inserta un ítem en el montículo y lo reordena.

En este caso insertamos el ítem al final del array y luego reordenamos hacia arriba desde el ítem insertado, intercambiando con el nodo padre en el camino hasta que el padre sea mayor en el caso de los MaxHeap, veamos mejor con la siguiente imagen de un MaxHeap en el cual insertamos un nodo resaltado en verde.

Si insertamos el nodo con valor (9) al final, ya no cumplimos la propiedad del MaxHeap porque el nodo insertado es mayor que el padre, por lo que debemos ir intercambiando nodos hacia arriba, hasta que se cumpla la condición de que el padre sea mayor que el hijo, el arreglo de ese árbol sería el siguiente: [10, 8, 6, 4, 2, 1, 9] Los pasos del algoritmo para el MaxHeap de la imagen serían:

1. Calcular el índice raíz a partir del índice del nodo insertado (9) su raíz sería el nodo (6)

2. Si el Padre es mayor que el hijo intercambiarlos, en este caso sí, Intercambiamos (9) y (6)

3. Repetir (iterativa o recursivamente) hasta que el padre sea mayor que el hijo.

Al final el Heap quedaría ordenado de la siguiente manera:

 

El arreglo sería [10, 8, 9, 4, 2, 1, 6]

RemoveTop() – Elimina un ítem del tope y lo retorna.

Para eliminar un nodo del tope intercambiamos el primer nodo raíz con el último y luego vamos verificando hacia abajo a partir del primer nodo que intercambiamos, algo muy importante es que debemos intercambiar el nodo raíz con el mayor de los nodos hijos porque en un MaxHeap ambos nodos deben ser menores que el padre. Heapify es implementado generalmente de forma recursiva.

En la imagen eliminaremos el nodo principal (10): Primero se intercambia con el último nodo (6) y se elimina.

[10, 8, 9, 4, 2, 1, 6]

Luego vamos verificando hacia abajo e intercambiamos con el mayor de los hijos.

[6, 8, 9, 4, 2, 1]

En este caso el mayor de los hijos es el nodo con valor (9) por lo que intercambiamos (6) con (9)

[9, 8, 6, 4, 2, 1]

Luego verificamos de nuevo, como (6) es mayor que (1) el algoritmo termina porque el padre es mayor que el hijo. Cabe destacar que gracias a la propiedad del MaxHeap, cada vez que se elimina un item el mayor de todos queda en el tope, esta es la base del algoritmo de ordenación HeapSort.

Ya para finalizar, la verdad me gustan mucho estos temas y he creado un repositorio en Github para implementar algunos de los algoritmos y estructuras de datos mas conocidas con la finalidad de aprender y mejorar. Dejo mi intento en C# de un Binary MaxHeap y MinHeap, en el código están desarrolladas todas las operaciones restantes con una pequeña explicación de cada una.

Referencias:

Heap: https://en.wikipedia.org/wiki/Heap_(data_structure)

Binary Heaps: https://en.wikipedia.org/wiki/Binary_heap

Implementación de un Heap en C#: Repositorio de Github