Búscalo aquí:

Heap Binario [código]


En esta ocasión quiero compartir información acerca de estructuras de datos, explícitamente el código en C++ de algunas estructuras de datos que implemente. En este post comparto el código en C++ de la estructura Heap Binario llamado también Montículo.



Para la implementación de colas de prioridad eficientes se hace uso de las estructuras tipo heap, ya sea el Heap Binario o Heap Binomial. El Heap Binario se basa en un arreglo de objetos vistos como un árbol binario casi completo y cumple características propias:

  • El árbol es completo en todos los niveles, excepto talvés en el último nivel, el cual esta lleno de izquierda a derecha.
  • La manera más eficiente de implementarlo es usando un arreglo que mantenga referencias a los elementos del árbol.
  • La raíz del árbol se almacena en A[1] y tiene en el índice i de un nodo, los índices de su padre e hijos se calcula de la siguiente manera: PADRE:= i/2 , IZQUIERDA:= 2i, DERECHA:=2i+1
  • La altura del heap es el número de enlaces del camino más largo para llegar a un nodo hoja. Las operaciones sobre el heap toman un tiempo proporcional a su altura (logarítmico).
  • Hay dos tipos de Heap Binario: Max Heap (la raíz almacena el elemento mayor) y Min Heap (la raíz almacena el elemento menor)

La implementación se realizó sobre la plataforma wxDEVC++ usando el compilador MingW de C++ haciendo uso de Programación Orientada a Objetos (POO) y de templates en C++ lo que permite hacer uso de diferentes tipos de objetos los cuales son almacenados en el Heap Binario para su posterior manipulación eficiente mediante las operaciones propias de dicha estructura de datos.

El código fue implementado junto con Dámaris Amaro y lo pueden DESCARGAR DESDE AQUI.



Quieres leer más post como éste???...suscribete aquí!!!

2 comentarios:

  1. Muchas gracias men! estoy viendo esta estructura de datos por primera vez y no sabia como implementarla bien! muchas gracias, sigue haciendo post tan buenos como este ;-)

    ResponderEliminar
  2. link caido, de todas maneras buena informacion.

    ResponderEliminar

Bienvenido a jcGeorge's Blog!!!

Por favor deja tu comentario, consulta o sugerencia, procura mantener habilitado tu perfil de Blogger o deja un enlace a tu blog o web.

Gracias por leer este blog!!!

Related Posts Plugin for WordPress, Blogger...