{"id":8245,"date":"2023-07-05T06:00:09","date_gmt":"2023-07-05T04:00:09","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8245"},"modified":"2023-07-07T10:58:13","modified_gmt":"2023-07-07T08:58:13","slug":"05-jul-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/05-jul-23\/","title":{"rendered":"El tipo abstracto de datos de las colas de prioridad"},"content":{"rendered":"<h3>1. El tipo abstracto de datos de las colas de prioridad<\/h3>\n<p>Una cola de prioridad es una cola en la que cada elemento tiene asociada una prioridad. La operaci\u00f3n de extracci\u00f3n siempre elige el elemento de menor prioridad.<\/p>\n<p>Las operaciones que definen a tipo abstracto de datos (TAD) de las colas de prioridad (cuyos elementos son del tipo a) son las siguientes:<\/p>\n<pre lang=\"text\">\n   vacia   :: Ord a => CPrioridad a\n   inserta :: Ord a => a -> CPrioridad a -> CPrioridad a\n   primero :: Ord a => CPrioridad a -> a\n   resto   :: Ord a => CPrioridad a -> CPrioridad a\n   esVacia :: Ord a => CPrioridad a -> Bool\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>vacia es la cola de prioridad vac\u00eda.<\/li>\n<li>(inserta x c) a\u00f1ade el elemento x a la cola de prioridad c.<\/li>\n<li>(primero c) es el primer elemento de la cola de prioridad c.<\/li>\n<li>(resto c) es el resto de la cola de prioridad c.<\/li>\n<li>(esVacia c) se verifica si la cola de prioridad c es vac\u00eda.<\/li>\n<\/ul>\n<p>Las operaciones tienen que verificar las siguientes propiedades:<\/p>\n<ul>\n<li>inserta x (inserta y c) == inserta y (inserta x c)<\/li>\n<li>primero (inserta x vacia) == x<\/li>\n<li>Si x &lt;= y, entonces primero (inserta y (inserta x c)) == primero (inserta x c)<\/li>\n<li>resto (inserta x vacia) == vacia<\/li>\n<li>Si x &lt;= y, entonces resto (inserta y (inserta x c)) == inserta y (resto (inserta x c))<\/li>\n<li>esVacia vacia<\/li>\n<li>not (esVacia (inserta x c))<\/li>\n<\/ul>\n<h3>2. Las colas de prioridad en Haskell<\/h3>\n<h4>2.1. El tipo abstracto de datos de las colas de prioridad en Haskell<\/h4>\n<p>El TAD de las colas de prioridadd se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/43a4s2V\">ColaDePrioridad.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\nmodule TAD.ColaDePrioridad\n  (CPrioridad,\n   vacia,   -- Ord a => CPrioridad a\n   inserta, -- Ord a => a -> CPrioridad a -> CPrioridad a\n   primero, -- Ord a => CPrioridad a -> a\n   resto,   -- Ord a => CPrioridad a -> CPrioridad a\n   esVacia, -- Ord a => CPrioridad a -> Bool\n  ) where\n\nimport TAD.ColaDePrioridadConListas\n<\/pre>\n<p>Para usar el TAD hay que usar una implementaci\u00f3n concreta. En principio,<br \/>\nsolo considearemos una que usa las listas.<\/p>\n<h4>2.2. Implementaci\u00f3n de las colas de prioridad mediante listas<\/h4>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3JMp22g\">ColaDePrioridadConListas.hs<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"haskell\">\n{-# LANGUAGE FlexibleInstances #-}\n{-# OPTIONS_GHC -fno-warn-unused-top-binds #-}\n\nmodule TAD.ColaDePrioridadConListas\n  (CPrioridad,\n   vacia,   -- Ord a => CPrioridad a\n   inserta, -- Ord a => a -> CPrioridad a -> CPrioridad a\n   primero, -- Ord a => CPrioridad a -> a\n   resto,   -- Ord a => CPrioridad a -> CPrioridad a\n   esVacia, -- Ord a => CPrioridad a -> Bool\n  ) where\n\nimport Test.QuickCheck\n\n-- Colas de prioridad mediante listas.\nnewtype CPrioridad a = CP [a]\n  deriving Eq\n\n-- (escribeColaDePrioridad c) es la cadena correspondiente a la cola de\n-- prioridad c. Por ejemplo,\n--    \u03bb> escribeColaDePrioridad (inserta 5 (inserta 2 (inserta 3 vacia)))\n--    \"2 | 3 | 5\"\nescribeColaDePrioridad :: Show a => CPrioridad a -> String\nescribeColaDePrioridad (CP [])     = \"-\"\nescribeColaDePrioridad (CP [x])    = show x\nescribeColaDePrioridad (CP (x:xs)) = show x ++ \" | \" ++ escribeColaDePrioridad (CP xs)\n\n-- Procedimiento de escritura de colas de prioridad.\ninstance Show a => Show (CPrioridad a) where\n  show = escribeColaDePrioridad\n\n-- Ejemplo de cola de prioridad\n--    \u03bb> inserta 5 (inserta 2 (inserta 3 vacia))\n--    2 | 3 | 5\n\n-- vacia es la cola de prioridad vac\u00eda. Por ejemplo,\n--    \u03bb> vacia\n--    CP []\nvacia :: Ord a => CPrioridad a\nvacia = CP []\n\n-- (inserta x c) es la cola obtenida a\u00f1adiendo el elemento x a la cola\n-- de prioridad c. Por ejemplo,\n--    \u03bb> inserta 5 (foldr inserta vacia [3,1,7,2,9])\n--    1 | 2 | 3 | 5 | 7 | 9\ninserta :: Ord a => a -> CPrioridad a -> CPrioridad a\ninserta x (CP q) = CP (ins x q)\n  where ins y []                   = [y]\n        ins y r@(e:r') | y < e     = y:r\n                       | otherwise = e:ins y r'\n\n-- (primero c) es el primer elemento de la cola de prioridad c. Por\n-- ejemplo,\n--    primero (foldr inserta vacia [3,1,7,2,9])  ==  1\nprimero :: Ord a => CPrioridad a -> a\nprimero (CP(x:_)) = x\nprimero _         = error \"primero: cola de prioridad vacia\"\n\n-- (resto c) es la cola de prioridad obtenida eliminando el primer\n-- elemento de la cola de prioridad c. Por ejemplo,\n--    \u03bb> resto (foldr inserta vacia [3,1,7,2,9])\n--    2 | 3 | 7 | 9\nresto :: Ord a => CPrioridad a -> CPrioridad a\nresto (CP (_:xs)) = CP xs\nresto _           = error \"resto: cola de prioridad vacia\"\n\n-- (esVacia c) se verifica si la cola de prioridad c es vac\u00eda. Por\n-- ejemplo,\n--    esVacia (foldr inserta vacia [3,1,7,2,9]) ==  False\n--    esVacia vacia                             ==  True\nesVacia :: Ord a => CPrioridad a -> Bool\nesVacia (CP xs) = null xs\n\n-- Generador de colas de prioridad\n-- ===============================\n\n-- genCPrioridad es un generador de colas de enteros. Por ejemplo,\n--    \u03bb> sample genCPrioridad\n--    -\n--    0 | 0\n--    4\n--    -4 | -3 | 6 | 6\n--    -7 | -6 | -2 | 0\n--    -10 | -10 | -5 | 1 | 4 | 6 | 6 | 9 | 10\n--    -\n--    -13 | -11 | -9 | -5 | -2 | -1 | 0 | 1 | 2 | 2 | 13 | 14\n--    -15 | -13 | -13 | -5 | -3 | -1 | 3 | 5 | 7 | 9 | 9 | 14 | 16\n--    -\n--    -17 | -15 | -14 | -5 | -2 | 1 | 1 | 2 | 5 | 7\ngenCPrioridad :: (Arbitrary a, Num a, Ord a) =>  Gen (CPrioridad a)\ngenCPrioridad = do\n  xs <- listOf arbitrary\n  return (foldr inserta vacia xs)\n\n-- El tipo cola de prioridad es una instancia del arbitrario.\ninstance (Arbitrary a, Num a, Ord a) => Arbitrary (CPrioridad a) where\n  arbitrary = genCPrioridad\n\n-- Propiedades de las colas de prioridad\n-- =====================================\n\n-- Propiedad. Si se a\u00f1ade dos elementos a una cola de prioridad se\n-- obtiene la misma cola de prioridad idependientemente del orden en\n-- que se a\u00f1adan los elementos.\nprop_inserta_conmuta :: Int -> Int -> CPrioridad Int -> Bool\nprop_inserta_conmuta x y c =\n  inserta x (inserta y c) == inserta y (inserta x c)\n\n-- Comprobaci\u00f3n.\n--    \u03bb> quickCheck prop_inserta_conmuta\n--    +++ OK, passed 100 tests.\n\n-- Propiedad. La cabeza de la cola de prioridad obtenida a\u00f1adiendo un\n-- elemento x a la cola de prioridad vac\u00eda es x.\nprop_primero_inserta_vacia :: Int -> CPrioridad Int -> Bool\nprop_primero_inserta_vacia x _ =\n  primero (inserta x vacia) == x\n\n-- Comprobaci\u00f3n.\n--    \u03bb> quickCheck prop_primero_inserta_vacia\n--    +++ OK, passed 100 tests.\n\n-- Propiedad. El primer elemento de una cola de prioridad c no cambia\n-- cuando se le a\u00f1ade un elemento mayor o igual que alg\u00fan elemento de c.\nprop_primero_inserta :: Int -> Int -> CPrioridad Int -> Property\nprop_primero_inserta x y c =\n  x <= y ==> primero (inserta y c') == primero c'\n  where c' = inserta x c\n\n-- Comprobaci\u00f3n.\n--    \u03bb> quickCheck prop_primero_inserta\n--    +++ OK, passed 100 tests.\n\n-- Propiedad. El resto de a\u00f1adir un elemento a la cola de prioridad\n-- vac\u00eda es la cola vac\u00eda.\nprop_resto_inserta_vacia :: Int -> Bool\nprop_resto_inserta_vacia x =\n  resto (inserta x vacia) == vacia\n\n-- Comprobaci\u00f3n.\n--    \u03bb> quickCheck prop_resto_inserta_vacia\n--    +++ OK, passed 100 tests.\n\n-- Propiedad. El resto de la cola de prioridad obtenida a\u00f1adiendo un\n-- elemento y a una cola c' (que tiene alg\u00fan elemento menor o igual que\n-- y) es la cola que se obtiene a\u00f1adiendo y al resto de c'.\nprop_resto_inserta :: Int -> Int -> CPrioridad Int -> Property\nprop_resto_inserta x y c =\n  x <= y ==> resto (inserta y c') == inserta y (resto c')\n  where c' = inserta x c\n\n-- Comprobaci\u00f3n:\n--    \u03bb> quickCheck prop_resto_inserta\n--    +++ OK, passed 100 tests.\n\n-- Propiedad. vacia es una cola vac\u00eda.\nprop_vacia_es_vacia :: Bool\nprop_vacia_es_vacia = esVacia (vacia :: CPrioridad Int)\n\n-- Comprobaci\u00f3n.\n--    \u03bb> quickCheck prop_vacia_es_vacia\n--    +++ OK, passed 100 tests.\n\n-- Propiedad. Si se a\u00f1ade un elemento a una cola de prioridad se obtiene\n-- una cola no vac\u00eda.\nprop_inserta_no_es_vacia :: Int -> CPrioridad Int -> Bool\nprop_inserta_no_es_vacia x c =\n  not (esVacia (inserta x c))\n\n-- Comprobaci\u00f3n.\n--    \u03bb> quickCheck prop_inserta_no_es_vacia\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h3>3. Las colas de prioridad en Python<\/h3>\n<h4>3.1. El tipo abstracto de las colas de prioridad en Python<\/h4>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3pFIxTy\">ColaDePrioridad.py<\/a> cuyo contenido es el siguiente:<\/p>\n<pre lang=\"python\">\n__all__ = [\n   'CPrioridad',\n   'vacia',\n   'inserta',\n   'primero',\n   'resto',\n   'esVacia',\n    ]\n\nfrom src.TAD.ColaDePrioridadConListas import (CPrioridad, esVacia, inserta,\n                                              primero, resto, vacia)\n<\/pre>\n<p>Para usar el TAD hay que usar una implementaci\u00f3n concreta. En principio, consideraremos solo una que usa las listas.<\/p>\n<h4>3.2. Implementaci\u00f3n de las colas de prioridad mediante listas<\/h4>\n<p>La implementaci\u00f3n se encuentra en el m\u00f3dulo <a href=\"https:\/\/bit.ly\/3PJXWg4\">ColaDePrioridadConListas.py<\/a> en el que se define la clase CPrioridad con los siguientes m\u00e9todos:<\/p>\n<ul>\n<li>inserta(x) a\u00f1ade x a la cola.<\/li>\n<li>primero() es el primero de la cola.<\/li>\n<li>resto() elimina el primero de la cola.<\/li>\n<li>esVacia() se verifica si la cola es vac\u00eda.<\/li>\n<\/ul>\n<p>Por ejemplo,<\/p>\n<pre lang=\"text\">\n   >>> c = CPrioridad()\n   >>> c\n   -\n   >>> c.inserta(5)\n   >>> c.inserta(2)\n   >>> c.inserta(3)\n   >>> c.inserta(4)\n   >>> c\n   2 | 3 | 4 | 5\n   >>> c.primero()\n   2\n   >>> c.resto()\n   >>> c\n   3 | 4 | 5\n   >>> c.esVacia()\n   False\n   >>> c = CPrioridad()\n   >>> c.esVacia()\n   True\n<\/pre>\n<p>Adem\u00e1s se definen las correspondientes funciones. Por ejemplo,<\/p>\n<pre lang=\"text\">\n   >>> vacia()\n   -\n   >>> inserta(4, inserta(3, inserta(2, inserta(5, vacia()))))\n   2 | 3 | 4 | 5\n   >>> primero (inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))\n   2\n   >>> resto (inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))\n   3 | 4 | 5\n   >>> esVacia(inserta(4, inserta(3, inserta(2, inserta(5, vacia())))))\n   False\n   >>> esVacia(vacia())\n   True\n<\/pre>\n<p>Finalmente, se define un generador aleatorio de colas de prioridad y se comprueba que las colas de prioridad cumplen las propiedades de su especificaci\u00f3n.<\/p>\n<pre lang=\"python\">\nfrom __future__ import annotations\n\n__all__ = [\n   'CPrioridad',\n   'vacia',\n   'inserta',\n   'primero',\n   'resto',\n   'esVacia',\n]\n\nfrom abc import abstractmethod\nfrom copy import deepcopy\nfrom dataclasses import dataclass, field\nfrom typing import Generic, Protocol, TypeVar\n\nfrom hypothesis import assume, given\nfrom hypothesis import strategies as st\n\n\nclass Comparable(Protocol):\n    @abstractmethod\n    def __lt__(self: A, otro: A) -> bool:\n        pass\n\nA = TypeVar('A', bound=Comparable)\n\n# Clase de las colas de prioridad mediante listas\n# ===============================================\n\n@dataclass\nclass CPrioridad(Generic[A]):\n    _elementos: list[A] = field(default_factory=list)\n\n    def __repr__(self) -> str:\n        \"\"\"\n        Devuelve una cadena con los elementos de la cola separados por \" | \".\n        Si la cola est\u00e1 vac\u00eda, devuelve \"-\".\n        \"\"\"\n        if not self._elementos:\n            return '-'\n        return ' | '.join(str(x) for x in self._elementos)\n\n    def esVacia(self) -> bool:\n        \"\"\"\n        Comprueba si la cola est\u00e1 vac\u00eda.\n\n        Devuelve True si la cola est\u00e1 vac\u00eda, False en caso contrario.\n        \"\"\"\n        return not self._elementos\n\n    def inserta(self, x: A) -> None:\n        \"\"\"\n        Inserta el elemento x en la cola de prioridad.\n        \"\"\"\n        self._elementos.append(x)\n        self._elementos.sort()\n\n    def primero(self) -> A:\n        \"\"\"\n        Devuelve el primer elemento de la cola.\n        \"\"\"\n        return self._elementos[0]\n\n    def resto(self) -> None:\n        \"\"\"\n        Elimina el primer elemento de la cola\n        \"\"\"\n        self._elementos.pop(0)\n\n# Funciones del tipo de las listas\n# ================================\n\ndef vacia() -> CPrioridad[A]:\n    \"\"\"\n    Crea y devuelve una cola vac\u00eda de tipo A.\n    \"\"\"\n    c: CPrioridad[A] = CPrioridad()\n    return c\n\ndef inserta(x: A, c: CPrioridad[A]) -> CPrioridad[A]:\n    \"\"\"\n    Inserta un elemento x en la cola c y devuelve una nueva cola con\n    el elemento insertado.\n    \"\"\"\n    _aux = deepcopy(c)\n    _aux.inserta(x)\n    return _aux\n\ndef esVacia(c: CPrioridad[A]) -> bool:\n    \"\"\"\n    Devuelve True si la cola est\u00e1 vac\u00eda, False si no lo est\u00e1.\n    \"\"\"\n    return c.esVacia()\n\ndef primero(c: CPrioridad[A]) -> A:\n    \"\"\"\n    Devuelve el primer elemento de la cola c.\n    \"\"\"\n    return c.primero()\n\ndef resto(c: CPrioridad[A]) -> CPrioridad[A]:\n    \"\"\"\n    Elimina el primer elemento de la cola c y devuelve una copia de la\n    cola resultante.\n    \"\"\"\n    _aux = deepcopy(c)\n    _aux.resto()\n    return _aux\n\n# Generador de colas de prioridad\n# ===============================\n\ndef colaAleatoria() -> st.SearchStrategy[CPrioridad[int]]:\n    \"\"\"\n    Genera una estrategia de b\u00fasqueda para generar colas de enteros de\n    forma aleatoria.\n\n    Utiliza la librer\u00eda Hypothesis para generar una lista de enteros y\n    luego se convierte en una instancia de la clase cola.\n    \"\"\"\n    return st.lists(st.integers()).map(CPrioridad)\n\n# Comprobaci\u00f3n de las propiedades de las colas\n# ============================================\n\n# Las propiedades son\n@given(c=colaAleatoria(), x=st.integers(), y=st.integers())\ndef test_cola1(c: CPrioridad[int], x: int, y: int) -> None:\n    assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c))\n    assert primero(inserta(x, vacia())) == x\n    assert resto(inserta(x, vacia())) == vacia()\n    assert esVacia(vacia())\n    assert not esVacia(inserta(x, c))\n\n@given(c=colaAleatoria(), x=st.integers(), y=st.integers())\ndef test_cola2(c: CPrioridad[int], x: int, y: int) -> None:\n    assume(not y < x)\n    assert primero(inserta(y, (inserta(x, c)))) == \\\n        primero(inserta(x,c))\n    assert resto(inserta(y, (inserta(x, c)))) == \\\n        inserta(y, resto(inserta(x, c)))\n\n# La comprobaci\u00f3n es\n#    > poetry run pytest -q ColaDePrioridadConListas.py\n#    2 passed in 0.54s\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>1. El tipo abstracto de datos de las colas de prioridad Una cola de prioridad es una cola en la que cada elemento tiene asociada una prioridad. La operaci\u00f3n de extracci\u00f3n siempre elige el elemento de menor prioridad. Las operaciones que definen a tipo abstracto de datos (TAD) de las colas de prioridad (cuyos elementos&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","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":[581],"tags":[590],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8245"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=8245"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8245\/revisions"}],"predecessor-version":[{"id":8246,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8245\/revisions\/8246"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8245"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8245"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8245"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}