Montículo binario

propuesto por josejuan

Montículo binario o "binary heap". Estructura optimizada para insertar eficientemente elementos en el montículo y recuperarlos rápidamente por prioridad (primero el menor o primero el mayor).

Enunciado
Se puede implementar de diferentes formas, dependiendo del contexto unas serán mejores que otras, más fáciles de implementar, etc...

Implementa tu heap binario y comenta las ventajas e inconvenientes frente a otras implementaciones posibles.

Sería deseable que tu heap permitiera al menos:

1. establecer de forma independiente el DATO y el valor (o clave) de ordenación (piensa que un heap de prioridad en el que la ordenación se base en el DATO no es muy útil).
2. insertar (si no se puede insertar, ¡no se puede usar!).
3. recuperar (eliminando) el elemento con mayor prioridad (sino, no sería muy útil, ¡sólo serviría para obtener el máximo en cada momento!).
4. que el dato "almacenable" pueda ser post-definido (no esté prefijado en la definición de tu heap; piensa que sino, tu heap sólo sirve para un tipo de dato concreto ¡y hay miles!).
5. que el tipo de la clave de ordenación se pueda post-definir (no esté prefijada en la definición de tu heap; piensa que sino, tu heap exige que definamos una función convesora para que sea útil ¡y no siempre es fácil!).

Otras funciones interesantes podrían ser:

b. que el tipo de ordenación (mín, máx) pueda seleccionarse. No es muy importante, porque suele ser fácil invertir las claves y porque sólo exigiría duplicar una única vez la definición de tu heap.


Más detalles aquí.

Ver todo el enunciado

Preguntas sobre el desafío

¿Tienes dudas sobre el desafío? plantéala aquí

Plantea tu pregunta

2 Soluciones

Dar mi solución

1voto
Montículo binario en Haskell
por

jneira

usando quickcheck hace 6 años

Mi version es una implementacion de la descripcion en seudocodigo del libro de texto "Programacion y estructura de datos avanzadas" en la que se usa un array como estructura de apoyo. Lo unico que la mia es pura funcional en lugar de imperativa.

1voto
Montículo binario en Haskell
por

josejuan

hace 6 años

Una forma sencilla de conseguir un heap binario no basado en arrays es almacenar el nº de nodos que contiene cada nodo; con ésto, las claves pueden ser arbitrariamente largas (sin necesidad de usar ninguna estructura alternativa). Quizás pueda hacerse con Rojo/Negro, pero no veo como alcanzar eficientemente las posiciones de interés (dónde insertar, de dónde sacar para eliminar).

Dar mi solución