Data.Heap

De Wikihaskell
Saltar a: navegación, buscar
Data.Heap
Data.Heap
Lenguaje Haskell
Biblioteca Data.Heap
Autores Juan Manuel Otero Albiol
Andrés Quintana López
Jose A. Brihuega Parodi

Contenido

Introducción

Data.Heap es una implementación de pilas bastante flexible basadas en funciones mínimo, máximo, mínima prioridad, máxima prioridad, cuyo autor es Stephan Friedrichs, que se basó en el libro de Chris Okasaki "Estructuras de datos puramente funcionales" (Cambridge University Press, 1998).

Existen diversas formas de tratar con las pilas, cada una de ellas a raíz de la estrategia elegida al ordenar sus elementos, por ejemplo:

- MinHeap o MaxHeap: es válida si se necesita almacenamiento dinámico. La pila mantiene siempre el máximo o mínimo elemento en la cabeza de la pila.

- MinPrioHeap o MaxPrioHeap: si se desea a mano introducir un valor en la pila con una prioridad estas son las pilas que debemos utilizar. Se introducen tuplas en la pila (prioridad, valor) de modo que sólo la prioridad (y no el valor) influye en el orden de elementos.

Y para mas utilidades diferentes, cabe la posibilidad de definir ordenes a medida para los elementos de la pila.

Todas de pilas antes mencionadas (MinHeap , MaxHeap, MinPrioHeap y MaxPrioHeap) se basan en el mismo tipo: HeapT prio val (prioridad, valor). Se trata de una pila simple de prioridad mínima. El truco es que nunca se inserta directamente pares. Sólo se inserta una "representación exterior" de un item y una instancia HeapItem adecuada se ocupa de dividir el elemento en una tupla (prio, val).

Instalación

Instalación de Cabal

Utilizaremos el gestor de paquetes [Cabal] para instalar nuestra librería.

  • Instalación de Cabal en Windows

El instalador de Cabal para Windows, se desgarga en desde su sitio oficial. Una vez instalado, sólo tendremos que añadirlo al PATH de Windows.

  • Instalación en Linux

En distribuciones de tipo Debian, instalamos Cabal usando el gestor de paquetes:

sudo apt-get install cabal-install cpphs

Instalación de Data.Heap

Desde Cabal, primero nos aseguraremos de tener las últimas actualizaciones:

sudo cabal update

Después. instalaremos nuestra librería con este comando:

sudo cabal --hugs --prefix=/usr install heap

Carga de la librería

Para comprobar que ya tenemos la librería en nuestro sistema, entramos en Hugs e intentamos importarla. Debemos usar la opción -98 para activar las extensiones de Hugs.

$ hugs -98
Hugs> :l Data.Heap
Data.Heap>

El prompt de Hugs indica que hemos cargado la librería.

Funciones

Tipos

data HeapT prioridad valor

Este tipo es la pila básica de la que derivan todas las demás. Se encarga de almacenar pares de prioridad-valor, manteniendo siempre el par de menor prioridad en la cabeza. La ordenación es siempre por prioridades, no por los valores de los elementos.

Instancias:

Typeable2 HeapT	 
Functor (HeapT prio)	 
Ord prio => Foldable (HeapT prio)	 
(Ord prio, Ord val) => Eq (HeapT prio val)	 
(Ord prio, Ord val) => Ord (HeapT prio val)	 
(Read prio, Read val, Ord prio) => Read (HeapT prio val)	 
(Show prio, Show val) => Show (HeapT prio val)	 
Ord prio => Monoid (HeapT prio val)


type Heap pol item = HeapT (Prio pol item) (Val pol item)

Este alias es una abreviatura de HeapT vista anteriormente, basado en HeapItem, la cual es la clase básica de ítems.

type MinHeap a = Heap MinPolicy a

Una Pila donde siempre va a extraer el elemento mínimo primero que exista.

type MaxHeap a = Heap MaxPolicy a

Una Pila donde se va a extraer el elemento máximo primero que exista.

type MinPrioHeap prioridad valor = Heap FstMinPolicy (prioridad, valor)

Una Pila de acopio pares prioridad de valor (prioridad, valor) . El orden de los elementos está determinado únicamente por la prioridad; el valor no tiene ninguna influencia. La pareja con prioridad mínima siempre se extrae primero.

type MaxPrioHeap prioridad valor = Heap FstMaxPolicy (prioridad, valor)

Igual que el anterior, pero en este caso la pareja prioridad-valor con la máxima prioridad siempre será extraída en primer lugar.

Estrategia de ordenación

class Ord (Prioridad pol item) => HeapItem pol item where

HeapItem pol item es una clase de tipo de artículos que se pueden almacenar en un HeapT . HeapT (prioridad valor) sólo proporciona mínima prioridad (es decir, valor no influye en el orden de los elementos y el par con un mínimo de prioridad se extrajo primero. El trabajo de esta clase sirve para traducir entre arbitraria item pares s y la prioridad de valor (Prioridad pol item, Valor pol item), dependiendo de la política pol que se utilizará. De esta manera, son capaces de utilizar HeapT no sólo como MinPrioHeap, sino también como MinHeap, MaxHeap, MaxPrioHeap o una implementación personalizada. En resumen: El trabajo de esta clase consiste en deconstruir arbitrariamente items en pares (prio, val) que pueden ser manejados por un mínimo de prioridad HeapT .

Ejemplo: Considere que desea utilizar HeapT prioridad valor como MaxHeap a. Usted tendría que invertir el orden de a (por ejemplo, mediante la introducción de InvOrd a y luego usar un type MaxHeap a = HeapT (InvOrd a) () . También habría que traducir cada x al (InvOrd x, ()) antes de la inserción y de vuelta después de la extracción con el fin de recuperar su tipo original a.

Esta funcionalidad es proporcionada por la clase HeapItem. En el ejemplo anterior, tendrá que utilizar un MaxHeap. La declaración de la instancia, por supuesto, ya prevista y se parece a esto (simplificado):

data MaxPolicy
 
instance (Ord a) => HeapItem MaxPolicy a where
     newtype Prio MaxPolicy a = MaxP a deriving (Eq)
     type    Val  MaxPolicy a = ()
     split x           = (MaxP x, ())
     merge (MaxP x, _) = x
 
instance (Ord a) => Ord (Prio MaxPolicy a) where
     compare (MaxP x) (MaxP y) = compare y x


MaxPolicy es un tipo "fantasma" que describe lo que HeapItem en realidad significaba (por ejemplo, tenemos que distinguir entre MinHeap y MaxHeap, que se realiza a través de MinPolicy y MaxPolicy, respectivamente) y MaxP invierte el orden de a , por lo que el máximo será la parte superior de la HeapT .

Las funciones de conversión de split y merge tiene que asegurarse de que

forall p v. split ( merge (p, v)) == (p, v) (merge y split no retira, agrega o altera cualquier cosa).

forall pv f. fst ( split ( merge (p, fv)) == fst ( split ( merge (p, v))) (modificando el valor asociado v no altera la prioridad p )


Tipos asociados:

data Prio pol item :: *

a parte del item que determina el orden de los elementos en un HeapT .

type Val pol item :: *

Todo lo que no parte de Prio pol item


Métodos:

split :: item -> (Prio pol item, Val pol item)

Traduce un item en un par de prioridades de valor.

merge :: (Prio pol item, Val pol item) -> item

Recupera el item de un par de prioridades de valor.


Instancias:

Ord a => HeapItem MaxPolicy a	 
Ord a => HeapItem MinPolicy a	 
Ord prio => HeapItem FstMaxPolicy (prio, val)
Ord prio => HeapItem FstMinPolicy (prio, val)


data MinPolicy

Tipo de ordenación para MinHeap

Instancias:

Ord a => HeapItem MinPolicy a	 
Eq a => Eq (Prio MinPolicy a)	 
Ord a => Ord (Prio MinPolicy a)	 
Read a => Read (Prio MinPolicy a)	 
Show a => Show (Prio MinPolicy a)


data MaxPolicy

Tipo de ordenación para MaxHeap

Instancias:

Ord a => HeapItem MaxPolicy a	 
Eq a => Eq (Prio MaxPolicy a)	 
Ord a => Ord (Prio MaxPolicy a)	 
Read a => Read (Prio MaxPolicy a)	 
Show a => Show (Prio MaxPolicy a)


data FstMinPolicy

Tipo de ordenación para (prio, val) MinPrioHeap.

Instancias:

Ord prio => HeapItem FstMinPolicy (prio, val)	 
Eq prio => Eq (Prio FstMinPolicy (prio, val))	 
Ord prio => Ord (Prio FstMinPolicy (prio, val))	 
Read prio => Read (Prio FstMinPolicy (prio, val))	 
Show prio => Show (Prio FstMinPolicy (prio, val))


data FstMaxPolicy

Tipo de ordenación para (prio, val) MaxPrioHeap..

Instancias:

Ord prio => HeapItem FstMaxPolicy (prio, val)	 
Eq prio => Eq (Prio FstMaxPolicy (prio, val))	 
Ord prio => Ord (Prio FstMaxPolicy (prio, val))	 
Read prio => Read (Prio FstMaxPolicy (prio, val))	 
Show prio => Show (Prio FstMaxPolicy (prio, val))

Consulta

Hay tres funciones para consultas básicas acerca del contenido del HeapT:

isEmpty :: HeapT prio val -> Bool

Comprueba si la pila está vacía.

null :: HeapT prio val -> Bool

Es equivalente a isEmpty.

size :: HeapT prio val -> Int

Indica el número de elementos contenido en la pila.

Construcción

Las siguientes funciones sirven para construir las pilas:

empty :: HeapT prio val

Genera una pila vacía.

singleton :: HeapItem pol item => item -> Heap pol item

Genera una pila con un único elemento.

insert :: HeapItem pol item => item -> Heap pol item -> Heap pol item

Inserta un ítem en una pila.

union :: Ord prio => HeapT prio val -> HeapT prio val -> HeapT prio val

Hace la unión de dos pilas.

unions :: Ord prio => [HeapT prio val] -> HeapT prio val

Hace la unión de una lista de pilas.

Destrucción

Con las siguientes funciones podemos destruir Pilas

view :: HeapItem pol item => Heap pol item -> Maybe (item, Heap pol item)

Busca el elemento con prioridad asociada mínima y la elimina de la pila (es decir, encontrar la inicio y la cola de la pila), si esta no está vacía. De lo contrario, se devuelve Nothing.

viewHead :: HeapItem pol item => Heap pol item -> Maybe item

Busca el elemento con prioridad asociada mínima en el inicio de la Pila, si no está vacía. De lo contrario, se devuelve Nothing.

viewTail :: HeapItem pol item => Heap pol item -> Maybe (Heap pol item)

Elimina el elemento con prioridad asociada mínima de la pila (es decir, su cola) si no está vacía. De lo contrario, se devuelve Nothing.

Filtro

Con un flitro, se eliminan todos los elementos de una pila que no cumplan un predicado especifico establecido.

filter :: HeapItem pol item => (item -> Bool) -> Heap pol item -> Heap pol item

Repartimos la pila en dos partes, dos grupos. Los del grupo h1 cumplen con el predicado del filtro, y los elementos del grupo h2, no.

partition :: HeapItem pol item => (item -> Bool) -> Heap pol item -> (Heap pol item, Heap pol item)

Subrangos

take :: HeapItem pol item => Int -> Heap pol item -> [item]

Toma los primeros n elementos de la pila

drop :: HeapItem pol item => Int -> Heap pol item -> Heap pol item

Elimina los primeros n elementos de la pila

splitAt :: HeapItem pol item => Int -> Heap pol item -> ([item], Heap pol item)

Devuelve una lista de los primeros n elementos de h, y h con esos elementos eliminados.

takeWhile :: HeapItem pol item => (item -> Bool) -> Heap pol item -> [item]

Incluye el fragmento inicial más largo de los elementos de h que satisfacen p.

dropWhile :: HeapItem pol item => (item -> Bool) -> Heap pol item -> Heap pol item

Elimina el fragmento inicial más largo de los elementos de h que satisfacen p.

span :: HeapItem pol item => (item -> Bool) -> Heap pol item -> ([item], Heap pol item)

Devuelve el fragmento inicial más largo de elementos de h que satisfacen p, y h con esos elementos eliminados.

break :: HeapItem pol item => (item -> Bool) -> Heap pol item -> ([item], Heap pol item)

El fragmento inciial más largo de los elementos de h que no satisfacen p, y h con esos elementos eliminados.

Conversión

Lista

fromList :: HeapItem pol item => [item] -> Heap pol item

Construye una pila de los objetos disponibles. Si suponemos que tenemos una lista ordenada, es probable que debamos utilizar fromDescList o fromAscList, que son más rápidas que esta función. Explicaremos el funcionamiento en el siguiente apartado.

toList :: HeapItem pol item => Heap pol item -> [item]

Incluiye un listado de la pila. No tiene un orden específico.

Lista ordenada

fromAscList :: HeapItem pol item => [item] -> Heap pol item

Crea una pila de una lista con sus elementos en orden ascendente de prioridad (es decir, en el mismo orden en que serán extraidos de la pila). Esta función es más rápida que fromlist pero no tan rápida como fromDescList. La condición inicial previa no se comprueba.

toAscList :: HeapItem pol item => Heap pol item -> [item]

Lista de los elementos de la pila en orden ascendente de prioridad.

fromDescList :: HeapItem pol item => [item] -> Heap pol item

Crea una pila de una lista con sus elementos en orden descendente de prioridad (es decir, se extraerán inversamente de la pila). Respecto a las funciones fromlist y fromAscList, esta es la más rápida. La condición previa tampoco se comprueba.

toDescList :: HeapItem pol item => Heap pol item -> [item]

Lista de los elementos de la pila en orden de prioridad. Debemos tener en cuenta que esta función no es especialmente eficiente (se implementa utilizando toAscList y invirtiendo la lista).

Ejemplos de uso

A pesar de su complejidad interna, el uso del tipo Heap es muy sencillo. La construcción de la estructura es inmediata a partir del predicado empty:

Data.Heap> insert 3 (empty :: MaxHeap Int)
fromList [3]

Observamos que siempre que construyamos una pila tenemos que especificar los tipos del "policy" (o marcador de prioridad) y de los datos a almacenar. En el siguiente ejemplo, hacemos lo mismo que en el anterior, pero con una sola llamada:

Data.Heap> singleton 3 :: MaxHeap Int
fromList [3]

Otra forma de construir es a través de una lista:

Data.Heap> Data.Heap.fromList [6,5,0,3] :: MinHeap Int
fromList [0,3,5,6]

El uso de las variantes MinPrioHeap y MaxPrioHeap nos permite indicar las prioridades arbitrariamente:

Data.Heap> insert ("Bajo",2) (singleton ("Alto",1) :: MinPrioHeap String Int)
fromList [("Alto",1),("Bajo",2)]

Son muy útiles las funciones de filtrado y partición. El predicado booleano a cumplir se lo podemos pasar en forma de función lambda:

Data.Heap> filter (\x -> mod x 2==0) (Data.Heap.fromList [1,2,5,7] :: MinHeap Int)
fromList [2]
Data.Heap> partition (\x -> mod x 2==0) (Data.Heap.fromList [1,2,5,7] :: MinHeap Int)
(fromList [2],fromList [1,5,7])

Referencias


Herramientas personales