La biblioteca de Haskell (Haskell.zip) debe descomprimirse en un directorio y después desde WinGHCi hacer referencia a ella a través de la orden:
Por ejemplo, si descomprimes Haskell.zip en el directorio de trabajo donde están la plantilla y el programa de prueba, la orden anterior es:Prelude> :set -idirectorioDondeSeEncuentraLaBiblioteca
EJERCICIO MONTICULOS MAXIFOBICOS HASKELL
Este ejercicio está tomado de http://programmingpraxis.com.
Los montículos Maxifóbicos (Maxophobics) son una variante de montículos zurdos, y ambos
permiten una implementación eficiente de una cola de prioridad.
En los zurdos, el peso del hijo izquierdo es siempre mayor o igual que el del derecho.
Como los zurdos, los maxifóbicos se representan por medio de árboles binarios aumentados, que
mantienen la propiedad de Heap Order, y por tanto, en cada nodo la clave es menor que las claves
de sus dos hijos. Por tanto el minElem se encuentra en la raíz del árbol. delMin descarta la raíz y
mezcla sus dos hijos e insert mezcla el árbol existente con un nuevo árbol con el elemento a
insertar como único elemento (singleton).
Los árboles zurdos son simples de utilizar y de codificar; es fácil demostrar que la mezcla de dos
montículos zurdos (resuelto en las transparencias) es zurdo, y de esta forma la longitud de su espina
derecha no supera al logaritmo del total de nodos de la mezcla, siendo ésta, salvo un factor de
proporcionalidad, una cota del número de operaciones de la mezcla. De aquí se deduce que las
operaciones de inserción y eliminación tienen complejidad logarítmica, ya que éstas se reducen a
una mezcla.
Los montículos maxifóbicos son una alternativa a los zurdos, pero no necesitan estar balanceados a
la izquierda (lo que libera del uso del invariante de los zurdos), y sin embargo las operaciones de
inserción y borrado tienen complejidad logarítmica. La diferencia de los montículos zurdos con los
maxifóbicos se encuentra en la operación de mezclar. En los maxifóbicos, la operación de mezcla se
implementa comparando los valores de las raíces de los dos árboles. La menor se mantiene como
valor de la raíz del montículo hm combinado resultado de la mezcla; el resto de la información se
distribuye en tres árboles: el montículo ganador de la comparación (que contendrá la clave mayor),
y los hijos del perdedor. De estos tres árboles se toma el mayor (con más nodos) y se coloca en la
rama derecha del montículo mezcla hm, colocándose en la rama izquierda la mezcla de los dos
restantes. De esta forma el montículo combinado contiene todas las claves de los originales y
además verifica la propiedad HO (heap order). Sorprendentemente un sencillo razonamiento
permite demostrar que esta mezcla tiene complejidad logarítmica (véase el artículo de Chris
Okasaki, “Alternatives to Two Classic Data Structures”, SIGCSE’05, February 23–27, 2005).
El nombre maxifóbico quiere decir “esquivando (o descartando) el mayor”: se mezclan los dos
menores subárboles.
a) Completa la implementación de las operaciones de estos montículos maxifóbicos, modificando lo
necesario en el código de los árboles zurdos (en DataStructures.Heap.MaxiphobicHeap).
b) (Difícil) La operación de mezcla de montículos maxifóbicos normalmente se implementa con
complejidad logarítmica por lo que es una implementación eficiente. Probar que efectivamente la
operación tiene complejidad logarítmica.
Ayuda: Sea T(N) el número de invocaciones a la función de mezcla para mezclar dos árboles
maxifóbicos cuyo número total de nodos de los dos subárboles es N. Intenta escribir una relación
de recurrencia para T(N) teniendo en cuenta que el mayor de los subárboles se ha evitado en cada
paso. Para calcular el tamaño total de los dos subárboles que se mezclarán (los dos más pequeños),
se debería primeramente determinar cuantos elementos tiene el subárbol evitado (el mayor).
c) Si interpretamos el tamaño (size) de un montículo maxifóbico como la altura del árbol, modifica el
código y estudia la complejidad de la operación de mezcla.
module MaxiphobicHeap
( Heap
, empty
, isEmpty
, minElem
, delMin
, insert -- puede definirse via merge
, merge
-- los siguientes son auxiliares
, mkHeap
-- , isHeap -- si exportamos leftChild, rightChild puede ser auxiliar
-- , verifyOP -- si exportamos leftChild, rightChild puede ser auxiliar
-- , drawOnWith
) where
-- import DrawTrees
import Test.QuickCheck
data Heap a = Empty | Node a Int (Heap a) (Heap a) deriving Show
-- number of elements
size :: Heap a -> Int
size Empty = 0
size (Node _ sz _ _) = sz
empty :: Heap a
empty = Empty
isEmpty :: Heap a -> Bool
isEmpty Empty = True
isEmpty _ = False
singleton :: a -> Heap a
singleton x = Node x 1 Empty Empty
insert :: (Ord a) => a -> Heap a -> Heap a
insert x h = merge (singleton x) h
minElem :: Heap a -> a
minElem Empty = error "minElem on empty heap"
minElem (Node x _ _ _) = x
delMin :: (Ord a) => Heap a -> Heap a
delMin Empty = error "delMin on empty heap"
delMin (Node _ _ lh rh) = merge lh rh
----------------------------------------------------------
---------------------------------------------------------
-- recursively merges smallest subheaps. Achieves O(log n) complexity
merge :: (Ord a) => Heap a -> Heap a -> Heap a
merge Empty h' = h'
merge h Empty = h
merge h@(Node x sz lh rh) h'@(Node x' sz' lh' rh')
| x < x' = Node x (sz+sz') smaller1 smaller2
| otherwise = merge h' h
where
smaller1
| ((size lh <= size rh)&&(size lh <= sz')) = lh
| ((size rh <= size lh)&&(size rh <= sz')) = rh
| otherwise = h'
smaller2
| ((size lh <= size rh)&&(size lh <= sz')) = merge rh h'
| ((size rh <= size lh)&&(size rh <= sz')) = merge lh h'
| otherwise = merge lh rh
----------------------------------------------------------
----------------------------------------------------------
-- Efficient O(n) bottom-up construction for heaps
mkHeap :: (Ord a) => [a] -> Heap a
mkHeap [] = empty
mkHeap xs = mergeLoop (map singleton xs)
where
mergeLoop [h] = h
mergeLoop hs = mergeLoop (mergePairs hs)
mergePairs [] = []
mergePairs [h] = [h]
mergePairs (h:h':hs) = merge h h' : mergePairs hs
{-
-------------------------------------------------------------------------------
-- Generating arbitrary Heaps
-------------------------------------------------------------------------------
instance (Ord a, Arbitrary a) => Arbitrary (Heap a) where
arbitrary = do
xs <- arbitrary
return (mkHeap xs)
-------------------------------------------------------------------------------
-- Invariants
-------------------------------------------------------------------------------
verifyOP :: (Ord a) => Heap a -> Bool
verifyOP Empty = True
verifyOP (Node x _ lh rh) = x `lessEq` lh && x `lessEq` rh
&& verifyOP lh && verifyOP rh
where
x `lessEq` Empty = True
x `lessEq` (Node x' _ _ _) = x<=x'
-------------------------------------------------------------------------------
-- Drawing a Heap
-------------------------------------------------------------------------------
instance Subtrees (Heap a) where
subtrees Empty = []
subtrees (Node _ _ lh rh) = [lh,rh]
instance (Show a) => ShowNode (Heap a) where
showNode (Node x _ _ _) = show x
drawOnWith :: FilePath -> (a -> String) -> Heap a -> IO ()
drawOnWith file toString = _drawOnWith file showHeap
where
showHeap (Node x _ _ _) = toString x
-}
----------------------------------------------------------------------------------------
------------------------------------para probar--------------------------------------
----------------------------------------------------------------------------------------
module MaxiphobicHeapDemos where
import Data.List(nub)
import MaxiphobicHeap
import DataStructures.Random
import DrawTrees
drawHeap :: (Show a) => Heap a -> IO ()
drawHeap = drawOn "MaxiphobicHeap.png"
outlineHeap :: Heap a -> IO ()
outlineHeap = outlineOn "MaxiphobicHeap.png"
drawCharHeap :: String -> IO ()
drawCharHeap xs = drawOnWith "MaxiphobicHeap.png" (\k -> [k]) (mkHeap xs)
drawIntHeap :: Heap Int -> IO ()
drawIntHeap h = drawOnWith "MaxiphobicHeap.png" (\k -> show k) h
randomHeap :: Int -> Seed -> Heap Int
randomHeap sz seed = mkHeap (take sz . nub . randoms $ seed)
randomHeapI (a,b) sz seed = mkHeap (take sz . nub . randomsR (a,b) $ seed)
-- take 10 $ randomsR (1,10) 32
demo1 sz seed = outlineHeap (randomHeap sz seed)
demoI (a,b) sz seed = drawIntHeap (randomHeapI (a,b) sz seed)
demo2 xs = drawHeap (mkHeap xs)
demo3 = drawCharHeap "murcielago"
{-
h1 = foldl (flip insert) empty [4,2,3,1,2,4,7,1]
instance (Ord a, Arbitrary a) => Arbitrary (Heap a) where
arbitrary = do
vs <- arbitrary
return (foldr insert empty vs)
isSorted :: (Ord a) => [a] -> Bool
isSorted [] = True
isSorted [x] = True
isSorted (x:y:zs) = x<=y && isSorted (y:zs)
p1 xs = isSorted ys && null (xs\\ys) && null(ys\\xs)
where
h = toHeap xs
ys = toList h
toHeap xs = foldr insert empty xs
toList h
| isEmpty h = []
| otherwise = minElem h : toList (delMin h)
-}
MISMO EJERCICIO EN JAVA
Implementa los montículos maxifóbicos en Java.
(dataStructures.heap.MaxiphobicHeap.java)
/**
* Binary Search trees implementation
*/
package tree;
import java.util.Iterator;
import java.util.NoSuchElementException;
import stack.Stack;
import stack.StackLink;
public class BST<K extends Comparable<? super K>, V> implements Iterable<K> { protected static class Tree<K, V> { protected K key; protected V value; protected Tree<K, V> left; protected Tree<K, V> right;
public Tree(K k, V v) { key = k; value = v; left = null; right = null; } }
private Tree<K, V> root;
public BST() { root = null; }
public boolean isEmpty() { return root == null; }
public void insert(K k, V v) { root = BST.insertRec(root, k, v); }
// returns modified tree private static <K extends Comparable<? super K>,V> Tree<K, V> insertRec(Tree<K, V> node, K key, V value) { if (node == null) node = new Tree<K, V>(key, value); else if (key.compareTo(node.key) == 0) node.value = value; else if (key.compareTo(node.key) < 0) node.left = insertRec(node.left, key, value); else node.right = insertRec(node.right, key, value); return node; }
public V search(K key) { return BST.searchRec(root, key); }
private static <K extends Comparable<? super K>,V> V searchRec(Tree<K, V> tree, K key) { if (tree == null) return null; else if (key.compareTo(tree.key) == 0) return tree.value; else if (key.compareTo(tree.key) < 0) return searchRec(tree.left, key); else return searchRec(tree.right, key); }
public boolean isElem(K key) { return search(key) != null; }
// pre: node is a non-empty tree // Removes minimum key (and value) from tree rooted at node. Before // deletion, key and value are saved into temp node. // returns modified tree (without min key and value) private static <K,V> Tree<K, V> split(Tree<K, V> node, Tree<K, V> temp) { if (node.left == null) { // min node found, so copy min key and value temp.key = node.key; temp.value = node.value; return node.right; // remove node } else { // remove min from left subtree node.left = split(node.left, temp); return node; } }
public void delete(K key) { root = BST.deleteRec(root, key); }
// returns modified tree private static <K extends Comparable<? super K>,V> Tree<K, V> deleteRec(Tree<K, V> node, K key) { if (node == null) ; // key not found; do nothing else if (key.compareTo(node.key) == 0) { if (node.left == null) node = node.right; else if (node.right == null) node = node.left; else /* * Tuple3<K,V,Tree<K,V>> tuple = split(node.right); node.key = * tuple._1(); node.value = tuple._2(); node.right = tuple._3(); */ node.right = split(node.right, node); } else if (key.compareTo(node.key) < 0) node.left = deleteRec(node.left, key); else node.right = deleteRec(node.right, key); return node; } // iterators
private abstract class Traversal implements Iterator<K> { Stack<K> stack = new StackLink<K>();
abstract void save(Tree<K, V> node);
public Traversal() { if (root != null) save(root); }
public boolean hasNext() { return !stack.isEmpty(); }
public K next() { if (!hasNext()) throw new NoSuchElementException();
K either = stack.top(); stack.pop(); return either; }
public void remove() { throw new UnsupportedOperationException(); }
}
public Iterator<K> inOrder() { return new Traversal() { void save(Tree<K, V> node) { // in reverse order, cause stack is LIFO if (node.right != null) save(node.right); stack.push(node.key); if (node.left != null) save(node.left); } }; }
public Iterator<K> postOrder() { return new Traversal() { void save(Tree<K, V> node) { // in reverse order, cause stack is LIFO stack.push(node.key); if (node.right != null) save(node.right); if (node.left != null) save(node.left); } }; }
public Iterator<K> preOrder() { return new Traversal() { void save(Tree<K, V> node) { // in reverse order, cause stack is LIFO if (node.right != null) save(node.right); if (node.left != null) save(node.left); stack.push(node.key); } }; }
public Iterator<K> iterator() { return inOrder(); }
}
BST
data TreeB a = EmptyB | NodeB a (TreeB a) (TreeB a) deriving Show
preOrderB :: TreeB a -> [a]
preOrderB EmptyB = []
preOrderB (NodeB x lt rt) = [x] ++ preOrderB lt ++ preOrderB rt
inOrderB :: TreeB a -> [a]
inOrderB EmptyB = []
inOrderB (NodeB x lt rt) = inOrderB lt ++ [x] ++ inOrderB rt
postOrderB :: TreeB a -> [a]
postOrderB EmptyB = []
postOrderB (NodeB x lt rt) = postOrderB lt ++ postOrderB rt ++ [x]
-- crea un arbol binario conocido su recorrido en preorden y enorden
-- findTreeB [2,1,3,4,6] [3,1,4,2,6]
-- ----> NodeB 2 (NodeB 1 (NodeB 3 EmptyB EmptyB) (NodeB 4 EmptyB EmptyB)) (NodeB 6 EmptyB EmptyB)
findTreeB :: Eq a => [a] -> [a] -> TreeB a
findTreeB [] _ = EmptyB
findTreeB (x:xs) ys = NodeB x (findTreeB is' is) (findTreeB ds' ds)
where
(is,ds) = span (/=x) ys --is es la rama izquierda y ds es la rama derecha
nts = length is
(is',ds') = splitAt nts xs
--span :: (a->Bool)->[a] -> ([a],[a]) Mientras se cumpla el predicado, va entrando elementos en la lista
--splitAt :: Int -> [a] -> ([a],[a]) Parte la lista
----------------------------------------------
JAVA
------------------------------------------------
/**
* Binary Search trees implementation
*/
package tree;
import java.util.Iterator;
import java.util.NoSuchElementException;
import stack.Stack;
import stack.StackLink;
public class BST<K extends Comparable<? super K>, V> implements Iterable<K> {
protected static class Tree<K, V> {
protected K key;
protected V value;
protected Tree<K, V> left;
protected Tree<K, V> right;
public Tree(K k, V v) {
key = k;
value = v;
left = null;
right = null;
}
}
private Tree<K, V> root;
public BST() {
root = null;
}
public boolean isEmpty() {
return root == null;
}
public void insert(K k, V v) {
root = BST.insertRec(root, k, v);
}
// returns modified tree
private static <K extends Comparable<? super K>,V> Tree<K, V> insertRec(Tree<K, V> node, K key, V value) {
if (node == null)
node = new Tree<K, V>(key, value);
else if (key.compareTo(node.key) == 0)
node.value = value;
else if (key.compareTo(node.key) < 0)
node.left = insertRec(node.left, key, value);
else
node.right = insertRec(node.right, key, value);
return node;
}
public V search(K key) {
return BST.searchRec(root, key);
}
private static <K extends Comparable<? super K>,V> V searchRec(Tree<K, V> tree, K key) {
if (tree == null)
return null;
else if (key.compareTo(tree.key) == 0)
return tree.value;
else if (key.compareTo(tree.key) < 0)
return searchRec(tree.left, key);
else
return searchRec(tree.right, key);
}
public boolean isElem(K key) {
return search(key) != null;
}
// pre: node is a non-empty tree
// Removes minimum key (and value) from tree rooted at node. Before
// deletion, key and value are saved into temp node.
// returns modified tree (without min key and value)
private static <K,V> Tree<K, V> split(Tree<K, V> node, Tree<K, V> temp) {
if (node.left == null) {
// min node found, so copy min key and value
temp.key = node.key;
temp.value = node.value;
return node.right; // remove node
} else {
// remove min from left subtree
node.left = split(node.left, temp);
return node;
}
}
public void delete(K key) {
root = BST.deleteRec(root, key);
}
// returns modified tree
private static <K extends Comparable<? super K>,V> Tree<K, V> deleteRec(Tree<K, V> node, K key) {
if (node == null)
; // key not found; do nothing
else if (key.compareTo(node.key) == 0) {
if (node.left == null)
node = node.right;
else if (node.right == null)
node = node.left;
else
/*
* Tuple3<K,V,Tree<K,V>> tuple = split(node.right); node.key =
* tuple._1(); node.value = tuple._2(); node.right = tuple._3();
*/
node.right = split(node.right, node);
} else if (key.compareTo(node.key) < 0)
node.left = deleteRec(node.left, key);
else
node.right = deleteRec(node.right, key);
return node;
}
// iterators
private abstract class Traversal implements Iterator<K> {
Stack<Either<K, Tree<K, V>>> stack = new StackLink<Either<K, Tree<K, V>>>();
abstract void save(Tree<K, V> node);
public Traversal() {
if (root != null)
save(root);
}
public boolean hasNext() {
return !stack.isEmpty();
}
public K next() {
if (!hasNext())
throw new NoSuchElementException();
Either<K, Tree<K, V>> either = stack.top();
stack.pop();
while (either.isRight()) {
Tree<K, V> node = either.right();
save(node);
either = stack.top();
stack.pop();
}
return either.left();
}
public void remove() {
throw new UnsupportedOperationException();
}
}
public Iterator<K> inOrder() {
return new Traversal() {
void save(Tree<K, V> node) {
// in reverse order, cause stack is LIFO
if (node.right != null)
stack.push(new Right<K, Tree<K, V>>(node.right));
stack.push(new Left<K, Tree<K, V>>(node.key));
if (node.left != null)
stack.push(new Right<K, Tree<K, V>>(node.left));
}
};
}
public Iterator<K> postOrder() {
return new Traversal() {
void save(Tree<K, V> node) {
// in reverse order, cause stack is LIFO
stack.push(new Left<K, Tree<K, V>>(node.key));
if (node.right != null)
stack.push(new Right<K, Tree<K, V>>(node.right));
if (node.left != null)
stack.push(new Right<K, Tree<K, V>>(node.left));
}
};
}
public Iterator<K> preOrder() {
return new Traversal() {
void save(Tree<K, V> node) {
// in reverse order, cause stack is LIFO
if (node.right != null)
stack.push(new Right<K, Tree<K, V>>(node.right));
if (node.left != null)
stack.push(new Right<K, Tree<K, V>>(node.left));
stack.push(new Left<K, Tree<K, V>>(node.key));
}
};
}
public Iterator<K> iterator() {
return inOrder();
}
}
No hay comentarios:
Publicar un comentario