basicamente, un heap es un arbol binario casi completo. Se le considera casi completo ya que se lleno en todos sus niveles,exepto, problamente, el ultimo que se va completando izquierda a derecha. la diferencia entre el arbol binario y heap es que en el segundo cada nodo tiene un valor menor o igual(o bien mayor o igual) que el valot asociado cada io de us hijos, lo que se conoce como condicio del heap.
¿Como diseñar el TDA que corresponde al arbol heap?
en el diseño del TDA para un heap se debe considerar que los elemntos que se almacenaron deben poseer la propiedad de ordenamiento, es decir, tener una relacion de mayor que y menor que.
Elemento: los elementos de un arbol heap son nodos. cada uno contiene un datos(simple o estructura tipoinfo) unico en el arbol.
Estructura: un arbol heap posee una estructura jerarquica(a expecion del arbol vacio). cada nodo contine un elemento de un conjunto ordenado valores; los nodos forman un arbol binario completo, de tal formaque cada padre contiene un elemento de mayor prioridad que sus dos hijos(la prioridad se establece con relacion a los valores almacenado, es decir, a menor valor, mayor prioridad, o a mayor, menor prioridad). La relacion de la prioridad se puede establecer como mayor o mayor-igual.
En un montículo de prioridad, el mayor elemento (o el menor, dependiendo de la relación de orden escogida) está siempre en el nodo raíz. Por esta razón, los montículos son útiles para implementar colas de prioridad. Una ventaja que poseen los montículos es que, por ser árboles completos, se pueden implementar usando arreglos, lo cual simplifica su codificación y libera al programador del uso de punteros.
¿Como genera un arbol heap a partir de un arreglo de elemento?
Esta operación parte de un elemento y lo inserta en un montículo aplicando su criterio de ordenación.Si suponemos que el monticulo está estructurado de forma que la raíz es mayor que sus hijos, comparamos el elemento a insertar (incluido en la primera posición libre) con su padre.Si el hijo es menor que el padre,entonces el elemento es insertado correctamente, si ocurre lo contrario sustituimos el hijo por el padre.
¿Y si la nueva raíz sigue siendo más grande que su nuevo padre?. Volvemos a hacer otra vez dicho paso hasta que el montículo quede totalmente ordenado. En la imagen adjunta vemos el ejemplo de cómo realmente se inserta un elemento en un montículo. Aplicamos la condición de que cada padre sea mayor que sus hijos, y siguiendo dicha regla el elemento a insertar es el 12. Es mayor que su padre, siguiendo el método de ordenación, sustituimos el elemento por su padre que es 9 y así quedaría el montículo ordenado.
Ahora veremos la implementación en varios lenguajes de programación del algoritmo de inserción de un elemento en un montículo.
¿Como se utilza una estructura Heap en una cola priorizada?
Si se considera que cada uno de los elementos en un heao tiene asociada una prioridad que depende de su valor(a menor valor, mayor prioridad), entoeces el elemento de mayor prioridad siempre estará en la raíz del árbol y los elementos que le siguen en estas caracteristicas estarán cerca de el.
Cuando se desee insertar un nuevo elemento en la cola priorizada, lo mas sencillo sera agregarlo como la ultima hoja del árbol, es decir, en la primera posición es libre del ultimo nivel.
No hay comentarios:
Publicar un comentario