I1M.Monticulo

TAD (tipo abstracto de datos) de los montículos.

Este módulo contiene el código del TAD de los montículos estudiado en el tema 20 del curso.

Un montículo 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 6 3 8 9 7 es un montículo, pero 1 / / 3 6 4 2 9 7 no lo es.

Documentation

data Monticulo a

El tipo de dato de los montículos.

Instances

Ord a => Eq (Monticulo a)

Defined in I1M.Monticulo

Methods

(==) :: Monticulo a -> Monticulo a -> Bool

(/=) :: Monticulo a -> Monticulo a -> Bool

Show a => Show (Monticulo a)

Defined in I1M.Monticulo

Methods

showsPrec :: Int -> Monticulo a -> ShowS

show :: Monticulo a -> String

showList :: [Monticulo a] -> ShowS

vacio :: Ord a => Monticulo a

vacio es el montículo vacío.

inserta :: Ord a => a -> Monticulo a -> Monticulo a

(inserta x m) es el montículo obtenido añadiendo el elemento x al montículo m. Por ejemplo,

ghci> inserta 3 (foldr inserta vacio [6,1,4,8])
M 1 2 
  (M 4 1 (M 8 1 Vacio Vacio) Vacio) 
  (M 3 1 (M 6 1 Vacio Vacio) Vacio)

menor :: Ord a => Monticulo a -> a

(menor m) es el menor elemento del montículo m. Por ejemplo,

menor (foldr inserta vacio [6,1,4,8])  ==  1
menor (foldr inserta vacio [7,5])      ==  5

resto :: Ord a => Monticulo a -> Monticulo a

(resto m) es el montículo obtenido eliminando el menor elemento del montículo m. Por ejemplo,

ghci> resto (foldr inserta vacio [6,1,4,8])
M 4 2 (M 8 1 Vacio Vacio) (M 6 1 Vacio Vacio)

esVacio :: Ord a => Monticulo a -> Bool

(esVacio m) se verifica si m es el montículo vacío.

valido :: Ord a => Monticulo a -> Bool

(valido m) se verifica si m es un montículo; es decir, es un árbol binario en el que los valores de cada nodo es menor o igual que los valores de sus hijos. Por ejemplo,

valido (foldr inserta vacio [6,1,4,8])    ==  True
valido (foldr inserta vacio [7,5])        ==  True
valido (M 3 5 (M 2 1 Vacio Vacio) Vacio)  ==  False