El tipo abstracto de datos de los montículos en Haskell
Continuando la serie dedicada a los tipos de datos abstractos (TAD) en Haskell, hoy le toca el turno a los montículos
Un montículo (heap en inglés) es un árbol binario en el que los valores de cada nodo es menor o igual que los valores de sus hijos. Por ejemplo,
|
1 2 3 4 5 6 |
1 1 / \ / \ / \ / \ 2 6 3 6 / \ / \ / \ / \ 3 8 9 7 4 2 9 7 |
el de la izquierda es un montículo, pero el de la derecha no lo es.
El contenido del resto del artículo es el siguiente:
- la signatura del TAD de los montículos;
- las propiedades del TAD de los montículos;
- la implementación, en Haskell, de los montículos mediante tipos de datos algebraicos;
- la comprobación con QuickCheck de sus propiedades y
- la implementación de las colas de prioridad mediante montículos.
Read More “El tipo abstracto de datos de los montículos en Haskell”