{"id":1529,"date":"2011-08-29T09:55:43","date_gmt":"2011-08-29T09:55:43","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/?p=1529"},"modified":"2013-03-31T07:24:00","modified_gmt":"2013-03-31T07:24:00","slug":"el-tipo-abstracto-de-datos-de-los-monticulos-en-haskell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/el-tipo-abstracto-de-datos-de-los-monticulos-en-haskell\/","title":{"rendered":"El tipo abstracto de datos de los mont\u00edculos en Haskell"},"content":{"rendered":"<p>Continuando la serie dedicada a los <a href=\"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/tag\/tipo-abstracto-de-datos\/\">tipos de datos abstractos (TAD) en Haskell<\/a>, hoy le toca el turno a los mont\u00edculos<\/p>\n<p>Un <a href=\"http:\/\/es.wikipedia.org\/wiki\/Mont\u00edculo_(inform\u00e1tica)\">mont\u00edculo<\/a> (<a href=\"http:\/\/en.wikipedia.org\/wiki\/Heap_(data_structure)\">heap<\/a> en ingl\u00e9s) es un \u00e1rbol binario en el que los valores de cada nodo es menor o igual que los valores de sus hijos. Por ejemplo,<\/p>\n<pre>\r\n        1              1     \r\n       \/ \\            \/ \\    \r\n      \/   \\          \/   \\   \r\n     2     6        3     6  \r\n    \/ \\   \/ \\      \/ \\   \/ \\ \r\n   3   8 9   7    4   2 9   7\r\n<\/pre>\n<p>el de la izquierda es un mont\u00edculo, pero el de la derecha no lo es.<\/p>\n<p>El contenido del resto del art\u00edculo es el siguiente: <\/p>\n<ul>\n<li>la signatura del TAD de los mont\u00edculos;\n<li>las propiedades del TAD de los mont\u00edculos;\n<li>la implementaci\u00f3n, en Haskell, de los mont\u00edculos mediante tipos de datos algebraicos;\n<li>la comprobaci\u00f3n con QuickCheck de sus propiedades y\n<li>la implementaci\u00f3n de las colas de prioridad mediante mont\u00edculos.\n<\/ul>\n<p><!--more--><\/p>\n<h3>La signatura del TAD de los mont\u00edculos<\/h3>\n<p>Las signatura de las operaciones del TAD de los mont\u00edculos son las siguientes:<\/p>\n<pre lang=\"haskell\">\r\nvacio   :: Ord a => Monticulo a\r\ninserta :: Ord a => a -> Monticulo a -> Monticulo a\r\nmenor   :: Ord a => Monticulo a -> a\r\nresto   :: Ord a => Monticulo a -> Monticulo a\r\nesVacio :: Ord a => Monticulo a -> Bool\r\nvalido  :: Ord a => Monticulo a -> Bool\r\n<\/pre>\n<p>con el siguiente significado<\/p>\n<ul>\n<li> <i>vacio<\/i> es el mont\u00edculo vac\u00edo.\n<li> <i>(inserta x m)<\/i> es el mont\u00edculo obtenido a\u00f1adiendo el elemento x al mont\u00edculo m.\n<li> <i>(menor m)<\/i> es el menor elemento del mont\u00edculo m.\n<li> <i>(resto m)<\/i> es el mont\u00edculo obtenido eliminando el menor elemento del mont\u00edculo m.\n<li> <i>(esVacio m)<\/i> se verifica si m es el mont\u00edculo vac\u00edo.\n<li> <i>(valido m)<\/i> se verifica si m es un mont\u00edculo; es decir, es un \u00e1rbol binario en el que los valores de cada nodo es menor o igual que los valores de sus hijos.\n<\/ul>\n<h3>Propiedades del TAD de los mont\u00edculos<\/h3>\n<p>Las propiedades son las siguientes:<\/p>\n<ol>\n<li> <tt>esVacio vacio<\/tt>\n<li> <tt>valido (inserta x m)<\/tt>\n<li> <tt>not (esVacio (inserta x m))<\/tt>\n<li> <tt>not (esVacio m) ==> valido (resto m)<\/tt>\n<li> <tt>resto (inserta x vacio) == vacio<\/tt>\n<li> <tt>x <= menor m ==> resto (inserta x m) == m<\/tt>\n<li> Si m es no vac\u00edo y x > menor m, entonces <tt>resto (inserta x m) == inserta x (resto m)<\/tt>\n<li> <tt>esVacio m || esVacio (resto m) || menor m <= menor (resto m)<\/tt>\n<\/ol>\n<h3>Implementaci\u00f3n de los mont\u00edculos mediante tipos de datos algebraicos<\/h3>\n<pre lang=\"haskell\">\r\nmodule Monticulo\r\n    (Monticulo,\r\n     vacio,   -- Ord a => Monticulo a\r\n     inserta, -- Ord a => a -> Monticulo a -> Monticulo a\r\n     menor,   -- Ord a => Monticulo a -> a\r\n     resto,   -- Ord a => Monticulo a -> Monticulo a\r\n     esVacio, -- Ord a => Monticulo a -> Bool\r\n     valido   -- Ord a => Monticulo a -> Bool\r\n    ) where \r\n\r\nimport Data.List (sort)\r\n\r\n-- Implementaci\u00f3n de mont\u00edculos mediante \u00e1rboles izquierdistas (\"leftist\r\n-- tree\"). \r\ndata Ord a => Monticulo a = Vacio\r\n                          | M a Int (Monticulo a) (Monticulo a)\r\n                            deriving Show\r\n\r\n-- Ejemplos de mont\u00edculos\r\n--    ghci> m1\r\n--    M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio) (M 6 1 Vacio Vacio)\r\n--    ghci> m2\r\n--    M 5 1 (M 7 1 Vacio Vacio) Vacio\r\n--    ghci> m3\r\n--    M 1 2 \r\n--      (M 5 2 \r\n--         (M 7 1 Vacio Vacio) \r\n--         (M 6 1 Vacio Vacio)) \r\n--      (M 4 1 \r\n--         (M 8 1 Vacio Vacio) \r\n--         Vacio)\r\n-- Gr\u00e1ficamente\r\n--            m1             m2                m3\r\n--        \r\n--                                             (1,2) \r\n--            (1,2)          (5,1)            \/     \\\r\n--           \/     \\        \/                \/       \\\r\n--        (4,1)   (6,1)  (7,1)           (5,2)        (4,1)\r\n--       \/                              \/     \\       \/\r\n--    (8,1)                          (7,1)   (6,1)  (8,1)\r\nm1, m1', m2, m3 :: Monticulo Int\r\nm1  = foldr inserta vacio [6,1,4,8]\r\nm1' = foldr inserta vacio [6,8,4,1]\r\nm2  = foldr inserta vacio [7,5]\r\nm3 = mezcla m1 m2\r\n\r\n-- vacio es el mont\u00edculo vac\u00edo.\r\nvacio :: Ord a => Monticulo a\r\nvacio = Vacio\r\n\r\n-- (rango m) es el rango del mont\u00edculo m; es decir, la menor distancia\r\n-- a un mont\u00edculo vac\u00edo. Por ejemplo,\r\n--    rango m1  ==  2\r\n--    rango m2  ==  1\r\nrango :: Ord a => Monticulo a -> Int\r\nrango Vacio       = 0\r\nrango (M _ r _ _) = r\r\n\r\n-- (creaM x a b) es el mont\u00edculo creado a partir del elemento x y los\r\n-- mont\u00edculos a y b. Se supone que x es menor o igual que el m\u00ednimo de\r\n-- a y de b. Por ejemplo,\r\n--    ghci> m1\r\n--    M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio) (M 6 1 Vacio Vacio)\r\n--    ghci> m2\r\n--    M 5 1 (M 7 1 Vacio Vacio) Vacio\r\n--    ghci> creaM 0 m1 m2\r\n--    M 0 2 (M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio) (M 6 1 Vacio Vacio)) \r\n--          (M 5 1 (M 7 1 Vacio Vacio) Vacio)\r\n--    ghci> creaM 0 m2 m1\r\n--    M 0 2 (M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio) (M 6 1 Vacio Vacio)) \r\n--          (M 5 1 (M 7 1 Vacio Vacio) Vacio)\r\ncreaM :: Ord a => a -> Monticulo a -> Monticulo a -> Monticulo a\r\ncreaM x a b | rango a >= rango b = M x (rango b + 1) a b\r\n            | otherwise          = M x (rango a + 1) b a\r\n\r\n-- (mezcla m1 m2) es el mont\u00edculo obtenido mezclando los mont\u00edculos m1 y\r\n-- m2. Por ejemplo,\r\n--    ghci> mezcla m1 m2\r\n--    M 1 2 \r\n--      (M 5 2 \r\n--         (M 7 1 Vacio Vacio) \r\n--         (M 6 1 Vacio Vacio)) \r\n--      (M 4 1 \r\n--         (M 8 1 Vacio Vacio) \r\n--         Vacio)\r\nmezcla :: Ord a =>  Monticulo a -> Monticulo a -> Monticulo a\r\nmezcla m Vacio = m\r\nmezcla Vacio m = m\r\nmezcla m1@(M x _ a1 b1) m2@(M y _ a2 b2)\r\n      | x <= y    = creaM x a1 (mezcla b1 m2)\r\n      | otherwise = creaM y a2 (mezcla m1 b2)\r\n\r\n-- (inserta x m) es el mont\u00edculo obtenido a\u00f1adiendo el elemento x al\r\n-- mont\u00edculo m. Por ejemplo, \r\n--    ghci> m1\r\n--    M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio) (M 6 1 Vacio Vacio)\r\n--    ghci> inserta 3 m1\r\n--    M 1 2 \r\n--      (M 4 1 (M 8 1 Vacio Vacio) Vacio) \r\n--      (M 3 1 (M 6 1 Vacio Vacio) Vacio)\r\ninserta :: Ord a => a -> Monticulo a -> Monticulo a\r\ninserta x m = mezcla (M x 1 Vacio Vacio) m\r\n\r\n-- (menor m) es el menor elemento del mont\u00edculo m. Por ejemplo, \r\n--   menor m1  ==  1\r\n--   menor m2  ==  5\r\nmenor  :: Ord a => Monticulo a -> a\r\nmenor (M x _ _ _) = x\r\nmenor Vacio       = error \"menor: monticulo vacio\"\r\n\r\n-- (resto m) es el mont\u00edculo obtenido eliminando el menor elemento del\r\n-- mont\u00edculo m. Por ejemplo, \r\n--    ghci> m1\r\n--    M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio) (M 6 1 Vacio Vacio)\r\n--    ghci> resto m1\r\n--    M 4 2 (M 8 1 Vacio Vacio) (M 6 1 Vacio Vacio)\r\nresto :: Ord a => Monticulo a -> Monticulo a\r\nresto Vacio       = error \"resto: monticulo vacio\"\r\nresto (M x _ a b) = mezcla a b\r\n\r\n-- (esVacio m) se verifica si m es el mont\u00edculo vac\u00edo.\r\nesVacio :: Ord a => Monticulo a -> Bool\r\nesVacio Vacio = True\r\nesVacio _     = False\r\n\r\n-- (valido m) se verifica si m es un mont\u00edculo; es decir, es un \u00e1rbol\r\n-- binario en el que los valores de cada nodo es menor o igual que los\r\n-- valores de sus hijos. Por ejemplo, \r\n--    valido m1  ==  True\r\n--    valido m2  ==  True\r\n--    valido m3  ==  True\r\n--    valido (M 3 5 (M 2 1 Vacio Vacio) Vacio)  ==  False\r\nvalido :: Ord a => Monticulo a -> Bool\r\nvalido Vacio = True\r\nvalido (M x _ Vacio Vacio) = True\r\nvalido (M x _ m1@(M x1 n1 a1 b1) Vacio) = \r\n    x <= x1 &#038;&#038; valido m1\r\nvalido (M x _ Vacio m2@(M x2 n2 a2 b2)) = \r\n    x <= x2 &#038;&#038; valido m2\r\nvalido (M x _ m1@(M x1 n1 a1 b1) m2@(M x2 n2 a2 b2)) = \r\n    x <= x1 &#038;&#038; valido m1 &#038;&#038;\r\n    x <= x2 &#038;&#038; valido m2\r\n\r\n-- (elementos m) es la lista de los elementos del mont\u00edculo m. Por\r\n-- ejemplo, \r\n--    elementos m1  ==  [1,4,8,6]\r\nelementos :: Ord a => Monticulo a -> [a]\r\nelementos Vacio       = []\r\nelementos (M x _ a b) = x : elementos a ++ elementos b\r\n\r\n-- (equivMonticulos m1 m2) se verifica si los mont\u00edculos m1 y m2 tienen\r\n-- los mismos elementos. Por ejemplo,\r\n--    ghci> m1\r\n--    M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio) (M 6 1 Vacio Vacio)\r\n--    ghci> m1'\r\n--    M 1 2 (M 4 1 Vacio Vacio) (M 6 1 (M 8 1 Vacio Vacio) Vacio)\r\n--    ghci> equivMonticulos m1 m1'\r\n--    True\r\nequivMonticulos :: Ord a => Monticulo a -> Monticulo a -> Bool\r\nequivMonticulos m1 m2 = \r\n    sort (elementos m1) == sort (elementos m2)\r\n\r\n-- Los mont\u00edculos son comparables por igualdad.\r\ninstance Ord a => Eq (Monticulo a) where\r\n   (==) = equivMonticulos\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Funciones auxiliares                                               --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (menorTodos x m) comprueba si x es menor que todos los elementos de m\r\nmenorTodos:: Ord a => a -> Monticulo a -> Bool\r\nmenorTodos x Vacio      = True\r\nmenorTodos x (M y n a b) = x <= y &#038;&#038; valido (M y n a b)\r\n\r\n-- (enMonticulo x m) se verifica si x es un elemento del mont\u00edculo\r\n-- m. Por ejemplo, \r\n--    enMonticulo 4 m1  ==  True\r\n--    enMonticulo 5 m1  ==  False\r\nenMonticulo x Vacio      = False\r\nenMonticulo x (M y _ a b) \r\n    | x < y     = False\r\n    | x == y    = True\r\n    | otherwise = enMonticulo x a || enMonticulo x b\r\n<\/pre>\n<h3>Propiedades de los mont\u00edculos<\/h3>\n<pre lang=\"haskell\">\r\n{-# LANGUAGE FlexibleInstances #-}\r\n\r\nimport Monticulo\r\n\r\nimport Test.QuickCheck\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Generador de mont\u00edculos                                            --\r\n-- ---------------------------------------------------------------------\r\n\r\n-- (creaMonticulo xs) es el mont\u00edculo correspondiente a la lista xs. Por\r\n-- ejemplo,\r\n--    ghci> creaMonticulo [6,1,4,8]\r\n--    M 1 2 (M 4 1 (M 8 1 Vacio Vacio) Vacio) (M 6 1 Vacio Vacio)\r\ncreaMonticulo :: [Int] -> Monticulo Int\r\ncreaMonticulo = foldr inserta vacio\r\n\r\n-- genMonticulo es un generador de mont\u00edculos. Por ejemplo,\r\n--    ghci> sample genMonticulo\r\n--    VacioM\r\n--    M (-1) 1 (M 1 1 VacioM VacioM) VacioM\r\n--    ...\r\ngenMonticulo :: Gen (Monticulo Int)\r\ngenMonticulo = do xs <- listOf arbitrary\r\n                  return (creaMonticulo xs)\r\n\r\n-- Mont\u00edculo es una instancia de la clase arbitraria.\r\ninstance Arbitrary (Monticulo Int) where\r\n    arbitrary = genMonticulo\r\n\r\n-- genMonticulo genera mont\u00edculos v\u00e1lidos.\r\nprop_genMonticulo :: Monticulo Int -> Bool\r\nprop_genMonticulo m = valido m\r\n\r\n-- Comprobaci\u00f3n.\r\n--    ghci> quickCheck prop_genMonticulo\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- monticuloNV es un generador de mont\u00edculos no vac\u00edo. Por ejemplo,\r\n--    ghci> sample monticuloNV\r\n--    M 0 1 VacioM VacioM\r\n--    M 1 1 (M 1 1 (M 1 1 VacioM VacioM) VacioM) VacioM\r\n--    M 0 2 (M 1 1 VacioM VacioM) (M 2 1 VacioM VacioM)\r\n--    M (-4) 2 (M (-3) 1 VacioM VacioM) (M 1 1 VacioM VacioM)\r\n--    M 3 1 VacioM VacioM\r\n--    M (-8) 1 (M (-5) 1 VacioM VacioM) VacioM\r\nmonticuloNV :: Gen (Monticulo Int)\r\nmonticuloNV = do xs <- listOf arbitrary\r\n                 x <- arbitrary\r\n                 return (creaMonticulo (x:xs))\r\n\r\n-- Prop. monticuloNV genera mont\u00edculos no vac\u00edo.\r\nprop_monticuloNV :: Monticulo Int -> Property\r\nprop_monticuloNV m =\r\n    forAll monticuloNV (\\m -> (valido m) && not (esVacio m))\r\n\r\n-- Comprobaci\u00f3n.\r\n--    *Main> quickCheck prop_monticuloNV\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- ---------------------------------------------------------------------\r\n-- Propiedades\r\n-- ---------------------------------------------------------------------\r\n\r\n-- Propiedades de vacio   \r\n-- --------------------\r\n\r\n-- Propiedad. vacio es un mont\u00edculo.\r\nprop_vacio_es_monticulo :: Bool\r\nprop_vacio_es_monticulo = \r\n    esVacio (vacio :: Monticulo Int)\r\n\r\n-- Comprobaci\u00f3n.\r\n--    ghci> prop_vacio_es_monticulo\r\n--    True\r\n\r\n-- Propiedades de inserta  \r\n-- ----------------------\r\n\r\n-- Propiedad. inserta produce mont\u00edculos v\u00e1lidos.\r\nprop_inserta_es_valida :: Int -> Monticulo Int -> Bool\r\nprop_inserta_es_valida x m =\r\n    valido (inserta x m)\r\n\r\n-- Comprobaci\u00f3n.\r\n--    ghci> quickCheck prop_inserta_es_valida\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Propiedad. Los mont\u00edculos creados con inserta son no vac\u00edo.\r\nprop_inserta_no_vacio :: Int -> Monticulo Int -> Bool\r\nprop_inserta_no_vacio x m =\r\n    not (esVacio (inserta x m))\r\n\r\n-- Comprobaci\u00f3n.\r\n--    ghci> quickCheck prop_inserta_no_vacio\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Propiedades de resto   \r\n-- --------------------\r\n\r\n-- Propiedad. Al borrar el menor elemento de un mont\u00edculo no vac\u00edo se\r\n-- obtiene un mont\u00edculo v\u00e1lido.\r\nprop_resto_es_valida :: Monticulo Int -> Property\r\nprop_resto_es_valida m =\r\n    forAll monticuloNV  (\\m -> valido (resto m))\r\n\r\n-- Comprobaci\u00f3n.\r\n--    ghci> quickCheck prop_resto_es_valida\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Propiedad. El resto de (inserta x m) es m si m es el mont\u00edculo vac\u00edo\r\n-- o x es menor o igual que el menor elemento de m o (inserta x (resto m)), \r\n-- en caso contrario. \r\nprop_resto_inserta :: Int -> Monticulo Int -> Bool\r\nprop_resto_inserta x m =\r\n    resto (inserta x m)\r\n    == if esVacio m || x <= menor m\r\n       then m\r\n       else inserta x (resto m)\r\n\r\n-- Comprobaci\u00f3n.\r\n--    ghci> quickCheck prop_resto_inserta\r\n--    +++ OK, passed 100 tests.\r\n\r\n-- Propiedades de menor  \r\n-- --------------------\r\n\r\n-- Propiedad. (menor m) es el menor elemento del mont\u00edculo m.\r\nprop_menor_es_minimo :: Monticulo Int -> Bool\r\nprop_menor_es_minimo m =\r\n    esVacio m ||\r\n    esVacio (resto m) ||\r\n    menor m <= menor (resto m)\r\n\r\n-- Comprobaci\u00f3n.\r\n--    ghci> quickCheck prop_menor_es_minimo\r\n--    +++ OK, passed 100 tests.\r\n<\/pre>\n<h3>Implementaci\u00f3n de las colas de prioridad mediante mont\u00edculos<\/h3>\n<pre lang=\"haskell\">\r\nmodule ColaDePrioridadConMonticulos \r\n    (CPrioridad,\r\n     vacia,   -- Ord a => CPrioridad a \r\n     inserta, -- Ord a => a -> CPrioridad a -> CPrioridad a \r\n     primero, -- Ord a => CPrioridad a -> a\r\n     resto,   -- Ord a => CPrioridad a -> CPrioridad a\r\n     esVacia, -- Ord a => CPrioridad a -> Bool \r\n     valida   -- Ord a => CPrioridad a -> Bool\r\n    ) where\r\n\r\nimport qualified Monticulo as M\r\n\r\n-- Colas de prioridad mediante mont\u00edculos.\r\nnewtype CPrioridad a = CP (M.Monticulo a)\r\n    deriving (Eq, Show)\r\n\r\n-- Ejemplo de cola de prioridad\r\n--    *Main> cp1\r\n--    CP (M 1 2 \r\n--          (M 2 2 \r\n--             (M 9 1 VacioM VacioM) \r\n--             (M 7 1 VacioM VacioM)) \r\n--          (M 3 1 VacioM VacioM))\r\ncp1 :: CPrioridad Int\r\ncp1 = foldr inserta vacia [3,1,7,2,9]\r\n\r\n-- vacia es la cola de prioridad vac\u00eda. Por ejemplo,\r\n--    vacia  ==  CP Vacio\r\nvacia :: Ord a => CPrioridad a \r\nvacia = CP M.vacio\r\n\r\n-- (inserta x c) a\u00f1ade el elemento x a la cola de prioridad c. Por ejemplo, \r\n--    ghci> cp1\r\n--    CP (M 1 2 \r\n--          (M 2 2 \r\n--             (M 9 1 VacioM VacioM) \r\n--             (M 7 1 VacioM VacioM)) \r\n--          (M 3 1 VacioM VacioM))\r\n--    ghci> inserta 5 cp1\r\n--    CP (M 1 2 \r\n--          (M 2 2 \r\n--             (M 9 1 VacioM VacioM) \r\n--             (M 7 1 VacioM VacioM)) \r\n--          (M 3 1 \r\n--             (M 5 1 VacioM VacioM) VacioM))\r\ninserta :: Ord a => a -> CPrioridad a -> CPrioridad a \r\ninserta v (CP c) = CP (M.inserta v c)\r\n\r\n-- (primero c) es la cabeza de la cola de prioridad c. Por ejemplo,\r\n--    primero cp1  ==  1\r\nprimero :: Ord a => CPrioridad a -> a\r\nprimero (CP c) = M.menor c\r\n\r\n-- (resto c) elimina la cabeza de la cola de prioridad c. Por ejemplo, \r\n--    ghci> cp1\r\n--    CP (M 1 2 \r\n--          (M 2 2 \r\n--             (M 9 1 VacioM VacioM) \r\n--             (M 7 1 VacioM VacioM)) \r\n--          (M 3 1 VacioM VacioM))\r\n--    ghci> resto cp1\r\n--    CP (M 2 2 \r\n--          (M 9 1 VacioM VacioM) \r\n--          (M 3 1 \r\n--             (M 7 1 VacioM VacioM) VacioM))\r\nresto :: Ord a => CPrioridad a -> CPrioridad a\r\nresto (CP c) = CP (M.resto c)\r\n\r\n-- (esVacia c) se verifica si la cola de prioridad c es vac\u00eda. Por\r\n-- ejemplo,   \r\n--    esVacia cp1    ==  False\r\n--    esVacia vacia  ==  True\r\nesVacia :: Ord a => CPrioridad a -> Bool \r\nesVacia (CP c) = M.esVacio c\r\n\r\n-- (valida c) se verifica si c es una cola de prioridad v\u00e1lida. En la\r\n-- representaci\u00f3n mediante mont\u00edculo todas las colas de prioridad son\r\n-- v\u00e1lidas. \r\nvalida :: Ord a => CPrioridad a -> Bool\r\nvalida _ = True\r\n<\/pre>\n<p>\nEl objetivo de la serie es la elaboraci\u00f3n de los temas de TAD del curso de <a href=\"http:\/\/www.cs.us.es\/~jalonso\/cursos\/i1m\">Inform\u00e1tica del Grado en Matem\u00e1ticas<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Continuando la serie dedicada a los tipos de datos abstractos (TAD) en Haskell, hoy le toca el turno a los mont\u00edculos Un mont\u00edculo (heap en ingl\u00e9s) es un \u00e1rbol binario en el que los valores de cada nodo es menor o igual que los valores de sus hijos. Por ejemplo, 1 1 \/ \\ \/&#8230;<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[5],"tags":[270,126,124],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_likes_enabled":false,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1529"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/comments?post=1529"}],"version-history":[{"count":3,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1529\/revisions"}],"predecessor-version":[{"id":3154,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/posts\/1529\/revisions\/3154"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/media?parent=1529"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/categories?post=1529"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/vestigium\/wp-json\/wp\/v2\/tags?post=1529"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}