Heap (estructura de datos)
En informática , un montón es una estructura de datos especializada basada en árboles que es esencialmente un árbol [1] casi completo que satisface la propiedad del montón : en un montón máximo , para cualquier nodo C dado , si P es un nodo padre de C, entonces la clave (el valor ) de P es mayor o igual que la clave de C. En un montón mínimo , la clave de P es menor o igual que la clave de C. [2] El nodo en la "parte superior" del montón (sin padres) se llama nodo raíz .
El montón es una implementación de máxima eficacia de un tipo de datos abstracto llamado cola de prioridad y, de hecho, las colas de prioridad a menudo se denominan "montones", independientemente de cómo se puedan implementar. En un montón, el elemento de prioridad más alta (o más baja) siempre se almacena en la raíz. Sin embargo, un montón no es una estructura ordenada; se puede considerar como parcialmente ordenado. Un montón es una estructura de datos útil cuando es necesario eliminar repetidamente el objeto con la prioridad más alta (o más baja), o cuando las inserciones deben intercalarse con eliminaciones del nodo raíz.
Una implementación común de un montón es el montón binario , en el que el árbol es un árbol binario (ver figura). La estructura de datos del montón, específicamente el montón binario, fue introducida por JWJ Williams en 1964, como una estructura de datos para el algoritmo de clasificación de heapsort . [3] Los montones también son cruciales en varios algoritmos de gráficos eficientes , como el algoritmo de Dijkstra . Cuando un montón es un árbol binario completo, tiene la altura más pequeña posible: un montón con N nodos y para cada nodo una rama siempre tiene log una altura de N.
Tenga en cuenta que, como se muestra en el gráfico, no hay un orden implícito entre hermanos o primos ni una secuencia implícita para un recorrido en orden (como habría, por ejemplo, en un árbol de búsqueda binario ). La relación de montón mencionada anteriormente se aplica solo entre los nodos y sus padres, abuelos, etc. El número máximo de hijos que puede tener cada nodo depende del tipo de montón.
Para un montón binario , en la matriz, el primer índice contiene el elemento raíz. Los dos índices siguientes de la matriz contienen los hijos de la raíz. Los siguientes cuatro índices contienen los cuatro hijos de los dos nodos hijos de la raíz, y así sucesivamente. Por lo tanto, dado un nodo en el índice i , sus hijos están en los índices y , y su padre está en el índice ⌊ ( i −1) / 2⌋ . Este sencillo esquema de indexación hace que sea eficaz para moverse "hacia arriba" o "hacia abajo" en el árbol.
El equilibrio de un montón se realiza mediante operaciones de tamizado hacia arriba o hacia abajo (intercambiando elementos que están fuera de servicio). Como podemos construir un montón a partir de una matriz sin requerir memoria adicional (para los nodos, por ejemplo), se puede usar heapsort para ordenar una matriz en el lugar.
