Montículo (informática) para niños
En computación, un montículo (también conocido como heap en inglés) es una estructura de datos especial que se parece a un árbol. Imagina un árbol donde cada "rama" (nodo padre) tiene una relación especial con sus "hojas" (nodos hijos).
Existen dos tipos principales de montículos:
- Montículos de máximos: Aquí, cada nodo padre siempre tiene un valor más grande que cualquiera de sus hijos. El valor más grande de todo el montículo siempre estará en la parte superior (la raíz).
- Montículos de mínimos: En este caso, cada nodo padre siempre tiene un valor más pequeño que cualquiera de sus hijos. El valor más pequeño de todo el montículo estará en la parte superior.
Un árbol se considera un montículo si cumple esta regla de ordenación y, además, es un árbol binario "casi completo". Esto significa que todos los niveles del árbol están llenos, excepto quizás el último, que se llena de izquierda a derecha.
Los montículos son muy útiles porque el elemento más importante (el más grande o el más pequeño, según el tipo de montículo) siempre está en la cima. Por eso, se usan mucho para crear colas de prioridad, donde los elementos se procesan según su importancia. Una gran ventaja es que, al ser árboles casi completos, se pueden guardar de forma sencilla en una lista (un "arreglo" o "array"), lo que facilita mucho su uso en programas de computadora.
Contenido
¿Cómo funcionan las operaciones en un montículo?
Las operaciones más comunes en un montículo son añadir un elemento y quitar un elemento. Estas operaciones están diseñadas para mantener siempre el orden especial del montículo.
¿Cómo se añade un elemento a un montículo?
Cuando queremos añadir un nuevo elemento a un montículo, lo primero que hacemos es colocarlo en la primera posición disponible en la parte de abajo del árbol.
Luego, para que el montículo siga ordenado, comparamos este nuevo elemento con su nodo padre.
- Si el nuevo elemento es más pequeño que su padre (en un montículo de máximos), ¡perfecto! Ya está en el lugar correcto.
- Si el nuevo elemento es más grande que su padre, entonces los intercambiamos de lugar. El nuevo elemento "flota" hacia arriba.
Este proceso de comparar e intercambiar se repite. El elemento sigue "flotando" hacia arriba, comparándose con su nuevo padre, hasta que encuentra un padre que es más grande que él (o hasta que llega a la cima del montículo). De esta manera, el montículo siempre mantiene su regla de que el padre es mayor que sus hijos.
En la imagen, puedes ver un ejemplo. Queremos insertar el número 12. Primero se coloca en la primera posición libre. Como 12 es mayor que su padre (9), se intercambian. Ahora 12 es el padre. Si 12 fuera mayor que su nuevo padre, el proceso continuaría.
¿Cómo se elimina un elemento de un montículo?
Normalmente, la operación de eliminar en un montículo se refiere a quitar el elemento más importante, que siempre está en la cima (la raíz).
Para eliminar el elemento de la raíz de un montículo de máximos (el más grande), seguimos estos pasos:
- Quitamos el elemento que está en la raíz (el más grande).
- El último elemento del montículo se mueve a la posición de la raíz, que ahora está vacía.
- Ahora, el nuevo elemento en la raíz podría no cumplir la regla del montículo (ser más grande que sus hijos). Para arreglar esto, comparamos este nuevo elemento con sus hijos. Si alguno de sus hijos es mayor, lo intercambiamos con el hijo más grande.
- Este proceso de comparar e intercambiar se repite. El elemento "se hunde" hacia abajo, comparándose con sus hijos, hasta que encuentra un lugar donde es más grande que sus hijos (o hasta que llega al final del montículo).
De esta forma, el montículo se reordena y sigue cumpliendo su propiedad de que el padre es mayor que sus hijos.
Usos importantes de los montículos
Además de las colas de prioridad, los montículos son fundamentales en un algoritmo de ordenación muy conocido llamado "ordenación por montículos" (heapsort). Este algoritmo usa las propiedades del montículo para organizar una lista de números de forma eficiente.
Véase también
En inglés: Heap (data structure) Facts for Kids
- Montículo binario
- Montículo binómico
- Montículo de Fibonacci
- Montículo suave
- Montículo 2-3
