Definición: ¿Qué significa Heap?
Un montón, en el contexto de la estructura de datos, es una estructura de datos basada en árboles que satisface la propiedad del montón, donde a cada elemento se le asigna un valor clave o ponderación. La clave de menor valor siempre tiene un nodo principal con una clave de mayor valor. Esto se denomina estructura de montón máximo y, entre todos los nodos, el nodo raíz tiene la clave más alta.
A veces, una estructura basada en árbol tiene una regla de estructura invertida, donde un elemento con una clave de mayor valor siempre tiene una clave de menor valor como nodo principal. Esto se denomina estructura min-heap y, entre todos los nodos, el nodo raíz tiene la clave más baja.
Techinfo explica Heap
No existen restricciones prácticas sobre el número de hijos que cada nodo puede tener en un montón, aunque cada nodo suele tener dos como máximo. El montón se considera la implementación más eficiente de un tipo de datos abstracto, conocido como cola de prioridad. La implementación del montón es esencial en varios algoritmos de gráficos (incluido el algoritmo de Dijkstra), así como en el algoritmo de clasificación de heapsort.
Los montones tienen varias variaciones que actúan como implementaciones de cola de prioridad de tipo de datos abstractos con alta eficiencia. Muchas aplicaciones, como los algoritmos de gráficos, requieren la implementación de colas de prioridad.
Una matriz es la forma de implementación más común de montón, donde no se necesitan punteros para vincular sus elementos.
Los montones realizan múltiples operaciones, que incluyen:
- Find-max: busca el nodo clave más alto entre un grupo de nodos
- Find-min: busca el nodo clave más bajo entre un grupo de nodos
- Delete-max: elimina el nodo clave más alto entre un grupo de nodos
- Delete-min: elimina el nodo clave más bajo entre un grupo de nodos
Los montones también incluyen funciones que realizan fusión, inserción y cambios de clave.
Esta definición se escribió en el contexto de la estructura de datos