Estructuras Lineales
Arboles Binarios
Arboles Enearios
Teoria de Grafos
Descargar Material
Un heap o montículo es una estructura de datos similar a un árbol binario de búsqueda pero ordenado de distinta forma por prioridades y además se representa siempre como un árbol binario completo representado como un arreglo.
Un montículo es un árbol binario completo tal que puede:
- Estar vacío
- El valor de la prioridad en la raíz es mayor, (menor) o igual que la prioridad de cualquiera de sus hijos.
- Ambos subárboles son montículos o heap.
Debe cumplir dos propiedades:
- Un árbol binario completamente lleno, con la posible excepción del nivel más bajo, el cual se rellena de izquierda a derecha. Estos árboles se denominan árboles binarios completos.
- Todo nodo debe ser mayor que todos sus descendientes. Por lo tanto, el maximo estará en la raíz y su búsqueda y eliminación se podrá realizar rápidamente.
Otras características:
- Todos los heaps son árboles binarios. No son necesariamente ABBs.
- El árbol está completamente balanceado excepto el último nivel, que debe estar lleno de izquierda a derecha.
- Para un elemento del heap en la posición k, sus hijos deberán estar en las posiciones 2k y 2k+1 del heap.
- Un HEAP puede representarse en un arreglo.
- Toda lista ordenada es un heap.
Pasos para insertar en un Heap:
- Agregamos el nodo. (de izquierda a derecha)
Comparamos son su padre.
- Si es mayor permutamos hasta llegar a la raíz
Repetimos el paso 1 y 2 hasta llenar el nivel.
Una vez llenado ese nivel pasamos al siguiente nivel.
Ejemplos de agregar:
Agregamos el 30:
Agregamos el 18:
Siempre se elimina la RAIZ
Pasos para eliminar:
- Eliminamos la raíz del heap
- Una vez eliminada remplazamos la raíz con el último nodo del último nivel.
- Comparamos si los hijos de la nueva raíz son menores.
- Si son menores no se hace ninguna permutación
Si son mayores (o uno de ellos) se hace permutación con el hijo mayor.
- Repetimos los pasos anteriores hasta no tener nodos para eliminar.
Ejemplo: Eliminar el 25
Eliminar el 24
Eliminar el 19
Eliminar el 18
El Árbol Heap (también conocido como Montículo) es un Árbol Binario con características particulares que determinan que cada Nodo padre tiene un valor mayor que el de cualquiera de sus nodos hijos, así como puede ser implementado en sentido contrario. Además de esta característica, este tipo de Árbol posee la propiedad de ser un Árbol Binario lleno, con la excepción de su último nivel el cual puede no encontrarse lleno y se va a ir llenando de izquierda a derecha.
La implementación de este Árbol se realizó en la Clase ArbolHeap, de una manera diferente a los demás, debido a que ha sido implementado utilizando un vector de acuerdo a los lineamientos de enseñanza por los que se guía el programa, y no con Nodos como se venían manejando las anteriores estructuras.
Como se puede observar en el siguiente diagrama de clases la representación de los datos se realiza por medio de un vector en el cual se almacenan los datos pertenecientes al Árbol. La inserción de los datos se realiza siempre en el ultimo nivel, realizando rotaciones (de ser necesario), de manera que el dato de mayor valor siempre se ubique en la raíz del Árbol para el momento que deba ser removido, ya que para este Árbol Heap, la extracción de los datos se realiza siempre eliminando la raíz del Árbol.
Requerimientos funcionales implementados para Arbol Heap:
RF1 - Crear un nuevo Árbol Heap.
RF2 - Conocer la raíz del Árbol Heap.
RF3 - Insertar nuevos datos en un Árbol Heap.
RF4 - Eliminar datos de un Árbol Heap, según las propiedades del Árbol.
RF5 - Conocer los datos existentes dentro del Árbol Heap por medio de un Array.
RF6 - Consultar la existencia de un dato dentro del Árbol Heap.
RF7 - Recorrer un Árbol Heap por niveles.
RF8 - Conocer el peso de un Árbol Heap.
RF9 - Consultar la altura de un Árbol Heap.
RF10 - Ordenar los datos de un Vector utilizando un Árbol Heap (HeapSort).
RF11 - Limpiar la información existente dentro del Árbol Heap.
RF12 - Conocer los datos existentes en el Árbol Heap por medio de una cadena.
Implementación de un Simulador para Arbol Heap:
El Simulador para ArbolHeap posee las operaciones indicadas por su menú de opciones dentro del mismo:
Recurso Documental para Proyecto de Grado SEED "Simuladores para Estudio de Estructuras de Datos"
Desarrolladores del Proyecto: Wilfred Uriel García - Cindy Yulieth Pabón Sánchez
2014