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.
