Monday, March 26, 2012

Heap

Heap se traduce como montículo, pero antes de hablar de estructuras de datos quiero definir que es un montículo, la verdad cuando yo leí la definición por primera vez no fui capaz de entender el concepto, así que lo quiero aclarar por si tu tuviste mi mismo problema:

Un montículo es una agrupación de cosas una sobre otras, en Colombia decimos de forma muy castiza “montonsito” o un bonche” de cosas. Asi que podemos hablar de montículos de frutas, monedas, arena, nueces, o cualquier cosa que se te ocurra.

Ahora si entrando en materia un Montículo es una estructura de datos en forma de árbol binario completo, el cual posee un algoritmo que organiza los nodos según su valor, ya sea en orden ascendente o descendente.

Recordemos que los árboles binarios poseen nodos que tienen máximo 2 nodos hijos, Un árbol binario es completo cuando los nodos de ambas ramas (izquierda y derecha) están balanceadas y ademas todos sus niveles están llenos excepto el último nivel, donde todos los nodos están hacia un mismo lado.

Maxheap: La cima contiene el elemento mayor y todos los hijos son menores que su padre (hijo<= padre), se observa como los números disminuyen a medida que descendemos en el montículo 


MinHeap: La cima contiene el elemento menor, todos los padres son menores que sus hijos (padre <=hijo) se observa como los números aumentan a medida que descendemos en el montículo



Si tienes información adicional sobre este tema, tus comentarios, dudas o enlaces de referencia serán bienvenidos.
Post a Comment