El tipo abstracto de datos de las colas de prioridad
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ón de extracción siempre elige el elemento de menor prioridad.
Las operaciones que definen a tipo abstracto de datos (TAD) de las colas de prioridad (cuyos elementos son del tipo a) son las siguientes:
|
1 2 3 4 5 |
vacia :: Ord a => CPrioridad a inserta :: Ord a => a -> CPrioridad a -> CPrioridad a primero :: Ord a => CPrioridad a -> a resto :: Ord a => CPrioridad a -> CPrioridad a esVacia :: Ord a => CPrioridad a -> Bool |
tales que
- vacia es la cola de prioridad vacía.
- (inserta x c) añade el elemento x a la cola de prioridad c.
- (primero c) es el primer elemento de la cola de prioridad c.
- (resto c) es el resto de la cola de prioridad c.
- (esVacia c) se verifica si la cola de prioridad c es vacía.
Las operaciones tienen que verificar las siguientes propiedades:
- inserta x (inserta y c) == inserta y (inserta x c)
- primero (inserta x vacia) == x
- Si x <= y, entonces primero (inserta y (inserta x c)) == primero (inserta x c)
- resto (inserta x vacia) == vacia
- Si x <= y, entonces resto (inserta y (inserta x c)) == inserta y (resto (inserta x c))
- esVacia vacia
- not (esVacia (inserta x c))
2. Las colas de prioridad en Haskell
2.1. El tipo abstracto de datos de las colas de prioridad en Haskell
El TAD de las colas de prioridadd se encuentra en el módulo ColaDePrioridad.hs cuyo contenido es el siguiente:
|
1 2 3 4 5 6 7 8 9 10 |
module TAD.ColaDePrioridad (CPrioridad, vacia, -- Ord a => CPrioridad a inserta, -- Ord a => a -> CPrioridad a -> CPrioridad a primero, -- Ord a => CPrioridad a -> a resto, -- Ord a => CPrioridad a -> CPrioridad a esVacia, -- Ord a => CPrioridad a -> Bool ) where import TAD.ColaDePrioridadConListas |
Para usar el TAD hay que usar una implementación concreta. En principio,
solo considearemos una que usa las listas.
2.2. Implementación de las colas de prioridad mediante listas
La implementación se encuentra en el módulo ColaDePrioridadConListas.hs cuyo contenido es el siguiente:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 |
{-# LANGUAGE FlexibleInstances #-} {-# OPTIONS_GHC -fno-warn-unused-top-binds #-} module TAD.ColaDePrioridadConListas (CPrioridad, vacia, -- Ord a => CPrioridad a inserta, -- Ord a => a -> CPrioridad a -> CPrioridad a primero, -- Ord a => CPrioridad a -> a resto, -- Ord a => CPrioridad a -> CPrioridad a esVacia, -- Ord a => CPrioridad a -> Bool ) where import Test.QuickCheck -- Colas de prioridad mediante listas. newtype CPrioridad a = CP [a] deriving Eq -- (escribeColaDePrioridad c) es la cadena correspondiente a la cola de -- prioridad c. Por ejemplo, -- λ> escribeColaDePrioridad (inserta 5 (inserta 2 (inserta 3 vacia))) -- "2 | 3 | 5" escribeColaDePrioridad :: Show a => CPrioridad a -> String escribeColaDePrioridad (CP []) = "-" escribeColaDePrioridad (CP [x]) = show x escribeColaDePrioridad (CP (x:xs)) = show x ++ " | " ++ escribeColaDePrioridad (CP xs) -- Procedimiento de escritura de colas de prioridad. instance Show a => Show (CPrioridad a) where show = escribeColaDePrioridad -- Ejemplo de cola de prioridad -- λ> inserta 5 (inserta 2 (inserta 3 vacia)) -- 2 | 3 | 5 -- vacia es la cola de prioridad vacía. Por ejemplo, -- λ> vacia -- CP [] vacia :: Ord a => CPrioridad a vacia = CP [] -- (inserta x c) es la cola obtenida añadiendo el elemento x a la cola -- de prioridad c. Por ejemplo, -- λ> inserta 5 (foldr inserta vacia [3,1,7,2,9]) -- 1 | 2 | 3 | 5 | 7 | 9 inserta :: Ord a => a -> CPrioridad a -> CPrioridad a inserta x (CP q) = CP (ins x q) where ins y [] = [y] ins y r@(e:r') | y < e = y:r | otherwise = e:ins y r' -- (primero c) es el primer elemento de la cola de prioridad c. Por -- ejemplo, -- primero (foldr inserta vacia [3,1,7,2,9]) == 1 primero :: Ord a => CPrioridad a -> a primero (CP(x:_)) = x primero _ = error "primero: cola de prioridad vacia" -- (resto c) es la cola de prioridad obtenida eliminando el primer -- elemento de la cola de prioridad c. Por ejemplo, -- λ> resto (foldr inserta vacia [3,1,7,2,9]) -- 2 | 3 | 7 | 9 resto :: Ord a => CPrioridad a -> CPrioridad a resto (CP (_:xs)) = CP xs resto _ = error "resto: cola de prioridad vacia" -- (esVacia c) se verifica si la cola de prioridad c es vacía. Por -- ejemplo, -- esVacia (foldr inserta vacia [3,1,7,2,9]) == False -- esVacia vacia == True esVacia :: Ord a => CPrioridad a -> Bool esVacia (CP xs) = null xs -- Generador de colas de prioridad -- =============================== -- genCPrioridad es un generador de colas de enteros. Por ejemplo, -- λ> sample genCPrioridad -- - -- 0 | 0 -- 4 -- -4 | -3 | 6 | 6 -- -7 | -6 | -2 | 0 -- -10 | -10 | -5 | 1 | 4 | 6 | 6 | 9 | 10 -- - -- -13 | -11 | -9 | -5 | -2 | -1 | 0 | 1 | 2 | 2 | 13 | 14 -- -15 | -13 | -13 | -5 | -3 | -1 | 3 | 5 | 7 | 9 | 9 | 14 | 16 -- - -- -17 | -15 | -14 | -5 | -2 | 1 | 1 | 2 | 5 | 7 genCPrioridad :: (Arbitrary a, Num a, Ord a) => Gen (CPrioridad a) genCPrioridad = do xs <- listOf arbitrary return (foldr inserta vacia xs) -- El tipo cola de prioridad es una instancia del arbitrario. instance (Arbitrary a, Num a, Ord a) => Arbitrary (CPrioridad a) where arbitrary = genCPrioridad -- Propiedades de las colas de prioridad -- ===================================== -- Propiedad. Si se añade dos elementos a una cola de prioridad se -- obtiene la misma cola de prioridad idependientemente del orden en -- que se añadan los elementos. prop_inserta_conmuta :: Int -> Int -> CPrioridad Int -> Bool prop_inserta_conmuta x y c = inserta x (inserta y c) == inserta y (inserta x c) -- Comprobación. -- λ> quickCheck prop_inserta_conmuta -- +++ OK, passed 100 tests. -- Propiedad. La cabeza de la cola de prioridad obtenida añadiendo un -- elemento x a la cola de prioridad vacía es x. prop_primero_inserta_vacia :: Int -> CPrioridad Int -> Bool prop_primero_inserta_vacia x _ = primero (inserta x vacia) == x -- Comprobación. -- λ> quickCheck prop_primero_inserta_vacia -- +++ OK, passed 100 tests. -- Propiedad. El primer elemento de una cola de prioridad c no cambia -- cuando se le añade un elemento mayor o igual que algún elemento de c. prop_primero_inserta :: Int -> Int -> CPrioridad Int -> Property prop_primero_inserta x y c = x <= y ==> primero (inserta y c') == primero c' where c' = inserta x c -- Comprobación. -- λ> quickCheck prop_primero_inserta -- +++ OK, passed 100 tests. -- Propiedad. El resto de añadir un elemento a la cola de prioridad -- vacía es la cola vacía. prop_resto_inserta_vacia :: Int -> Bool prop_resto_inserta_vacia x = resto (inserta x vacia) == vacia -- Comprobación. -- λ> quickCheck prop_resto_inserta_vacia -- +++ OK, passed 100 tests. -- Propiedad. El resto de la cola de prioridad obtenida añadiendo un -- elemento y a una cola c' (que tiene algún elemento menor o igual que -- y) es la cola que se obtiene añadiendo y al resto de c'. prop_resto_inserta :: Int -> Int -> CPrioridad Int -> Property prop_resto_inserta x y c = x <= y ==> resto (inserta y c') == inserta y (resto c') where c' = inserta x c -- Comprobación: -- λ> quickCheck prop_resto_inserta -- +++ OK, passed 100 tests. -- Propiedad. vacia es una cola vacía. prop_vacia_es_vacia :: Bool prop_vacia_es_vacia = esVacia (vacia :: CPrioridad Int) -- Comprobación. -- λ> quickCheck prop_vacia_es_vacia -- +++ OK, passed 100 tests. -- Propiedad. Si se añade un elemento a una cola de prioridad se obtiene -- una cola no vacía. prop_inserta_no_es_vacia :: Int -> CPrioridad Int -> Bool prop_inserta_no_es_vacia x c = not (esVacia (inserta x c)) -- Comprobación. -- λ> quickCheck prop_inserta_no_es_vacia -- +++ OK, passed 100 tests. |
3. Las colas de prioridad en Python
3.1. El tipo abstracto de las colas de prioridad en Python
La implementación se encuentra en el módulo ColaDePrioridad.py cuyo contenido es el siguiente:
|
1 2 3 4 5 6 7 8 9 10 11 |
__all__ = [ 'CPrioridad', 'vacia', 'inserta', 'primero', 'resto', 'esVacia', ] from src.TAD.ColaDePrioridadConListas import (CPrioridad, esVacia, inserta, primero, resto, vacia) |
Para usar el TAD hay que usar una implementación concreta. En principio, consideraremos solo una que usa las listas.
3.2. Implementación de las colas de prioridad mediante listas
La implementación se encuentra en el módulo ColaDePrioridadConListas.py en el que se define la clase CPrioridad con los siguientes métodos:
- inserta(x) añade x a la cola.
- primero() es el primero de la cola.
- resto() elimina el primero de la cola.
- esVacia() se verifica si la cola es vacía.
Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
>>> c = CPrioridad() >>> c - >>> c.inserta(5) >>> c.inserta(2) >>> c.inserta(3) >>> c.inserta(4) >>> c 2 | 3 | 4 | 5 >>> c.primero() 2 >>> c.resto() >>> c 3 | 4 | 5 >>> c.esVacia() False >>> c = CPrioridad() >>> c.esVacia() True |
Además se definen las correspondientes funciones. Por ejemplo,
|
1 2 3 4 5 6 7 8 9 10 11 12 |
>>> vacia() - >>> inserta(4, inserta(3, inserta(2, inserta(5, vacia())))) 2 | 3 | 4 | 5 >>> primero (inserta(4, inserta(3, inserta(2, inserta(5, vacia()))))) 2 >>> resto (inserta(4, inserta(3, inserta(2, inserta(5, vacia()))))) 3 | 4 | 5 >>> esVacia(inserta(4, inserta(3, inserta(2, inserta(5, vacia()))))) False >>> esVacia(vacia()) True |
Finalmente, se define un generador aleatorio de colas de prioridad y se comprueba que las colas de prioridad cumplen las propiedades de su especificación.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 |
from __future__ import annotations __all__ = [ 'CPrioridad', 'vacia', 'inserta', 'primero', 'resto', 'esVacia', ] from abc import abstractmethod from copy import deepcopy from dataclasses import dataclass, field from typing import Generic, Protocol, TypeVar from hypothesis import assume, given from hypothesis import strategies as st class Comparable(Protocol): @abstractmethod def __lt__(self: A, otro: A) -> bool: pass A = TypeVar('A', bound=Comparable) # Clase de las colas de prioridad mediante listas # =============================================== @dataclass class CPrioridad(Generic[A]): _elementos: list[A] = field(default_factory=list) def __repr__(self) -> str: """ Devuelve una cadena con los elementos de la cola separados por " | ". Si la cola está vacía, devuelve "-". """ if not self._elementos: return '-' return ' | '.join(str(x) for x in self._elementos) def esVacia(self) -> bool: """ Comprueba si la cola está vacía. Devuelve True si la cola está vacía, False en caso contrario. """ return not self._elementos def inserta(self, x: A) -> None: """ Inserta el elemento x en la cola de prioridad. """ self._elementos.append(x) self._elementos.sort() def primero(self) -> A: """ Devuelve el primer elemento de la cola. """ return self._elementos[0] def resto(self) -> None: """ Elimina el primer elemento de la cola """ self._elementos.pop(0) # Funciones del tipo de las listas # ================================ def vacia() -> CPrioridad[A]: """ Crea y devuelve una cola vacía de tipo A. """ c: CPrioridad[A] = CPrioridad() return c def inserta(x: A, c: CPrioridad[A]) -> CPrioridad[A]: """ Inserta un elemento x en la cola c y devuelve una nueva cola con el elemento insertado. """ _aux = deepcopy(c) _aux.inserta(x) return _aux def esVacia(c: CPrioridad[A]) -> bool: """ Devuelve True si la cola está vacía, False si no lo está. """ return c.esVacia() def primero(c: CPrioridad[A]) -> A: """ Devuelve el primer elemento de la cola c. """ return c.primero() def resto(c: CPrioridad[A]) -> CPrioridad[A]: """ Elimina el primer elemento de la cola c y devuelve una copia de la cola resultante. """ _aux = deepcopy(c) _aux.resto() return _aux # Generador de colas de prioridad # =============================== def colaAleatoria() -> st.SearchStrategy[CPrioridad[int]]: """ Genera una estrategia de búsqueda para generar colas de enteros de forma aleatoria. Utiliza la librería Hypothesis para generar una lista de enteros y luego se convierte en una instancia de la clase cola. """ return st.lists(st.integers()).map(CPrioridad) # Comprobación de las propiedades de las colas # ============================================ # Las propiedades son @given(c=colaAleatoria(), x=st.integers(), y=st.integers()) def test_cola1(c: CPrioridad[int], x: int, y: int) -> None: assert inserta(x, inserta(y, c)) == inserta(y, inserta(x, c)) assert primero(inserta(x, vacia())) == x assert resto(inserta(x, vacia())) == vacia() assert esVacia(vacia()) assert not esVacia(inserta(x, c)) @given(c=colaAleatoria(), x=st.integers(), y=st.integers()) def test_cola2(c: CPrioridad[int], x: int, y: int) -> None: assume(not y < x) assert primero(inserta(y, (inserta(x, c)))) == \ primero(inserta(x,c)) assert resto(inserta(y, (inserta(x, c)))) == \ inserta(y, resto(inserta(x, c))) # La comprobación es # > poetry run pytest -q ColaDePrioridadConListas.py # 2 passed in 0.54s |