Montón (estructura de datos)
En informática , un montón es una estructura de datos basada en un árbol especializado 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 principal 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 "superior" del montón (sin padres) se denomina nodo raíz .
El montón es una implementación de máxima eficiencia 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 implementen. 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; puede considerarse 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 las 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 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 ramas para cada nodo siempre tiene una altura de registro 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 lo habría, por ejemplo, en un árbol de búsqueda binaria ). 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 siguientes dos índices de la matriz contienen los hijos de la raíz. Los cuatro índices siguientes 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 eficiente moverse "hacia arriba" o "hacia abajo" en el árbol.
El equilibrio de un montón se realiza mediante operaciones de cribado ascendente o descendente (intercambio de 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.
