Montículo (programación)
De Wikipedia, la enciclopedia libre
- Este artículo discute la estructura de datos montículo. Para consultar sobre el lugar de donde se asigna memoria dinámica véase Manejo dinámico de memoria.
En computación, un montículo (heap en inglés) es una estructura de Árbol con información perteneciente a un conjunto ordenado. Los montículos tienen la característica de que cada nodo tiene un valor mayor que el de todos sus nodos hijos.
Sean A y B dos nodos de un montículo tal que B es un hijo de A. El montículo debe entonces satisfacer la siguiente condición (Propiedad de montículo):
- clave(A) ≥ clave(B)
Ésta es la única restricción en los montículos. Ella implica que el mayor elemento (o el menor, dependiendo de la relación de orden escogida) está siempre en el nodo raíz. Debido a esto, los montículos se utilizan para implementar colas de prioridad. La eficiencia de las operaciones en los montículos es crucial en diversos algoritmos de recorrido de grafos y de ordenamiento (Heapsort).
Las operaciones normalmente utilizadas en un montículo son la inserción de un elemento cualquiera y la eliminación del máximo (el elemento de la raíz).
[editar] Variantes
- Montículo binario
- Montículo binómico
- Heap de Fibonacci
- Montículo suave
- Montículo 2-3
