[Haskell-cafe] Who lives in a heap like this?

[Rodrigo Queiro]

I think (although I am far from an expert) that it is a skew heap, based on
this: http://www.palgrave.com/pdfs/0333992857.pdf

On 19/05/07, Andrew Coppin <andrewcoppin at btinternet.com> wrote:
>
> Greetings.
>
> I have just implemented a heap. But... um... I can't acutally figure out
> *which kind* of heap it is! LOL. Any ideas?
>
> (Seems to work really well, whatever it is. Oh, and I discovered that
> you can sort data just by shoving it all into a heap, and then taking it
> all out again. Apparently this is a standard algorithm, and it's known
> as a "heap sort", unsurprisingly. You learn something every day...)
>
>
> module Heap where
>
> import Data.List (intersperse, unfoldr)
>
> data Heap t = Node !t !(Heap t) !(Heap t) | Null
>
> instance (Show t) => Show (Heap t) where
>   show = work "" where
>     work p (Null) = p ++ "-"
>     work p (Node v t0 t1) = concat $ intersperse "\n" $ [work (' ':p)
> t0, p ++ show v, work (' ':p) t1]
>
> empty = Null
>
> is_empty Null = True
> is_empty _    = False
>
> insert v (Null) = Node v Null Null
> insert v (Node v0 t0 t1) =
>   let lo = min v v0
>       hi = max v v0
>   in  Node hi (insert lo t1) t0
>
> get_max (Null) = error "heap is empty"
> get_max (Node v _ _) = v
>
> delete_max (Null) = error "heap is empty"
> delete_max (Node _ Null Null) = Null
> delete_max (Node _ Null t1)   = t1
> delete_max (Node _ t0   Null) = t0
> delete_max (Node _ t0   t1)
>   | get_max t0 > get_max t1 = Node (get_max t0) (delete_max t0)      t1
>   | otherwise               = Node (get_max t1)             t0
> (delete_max t1)
>
> size (Null) = 0
> size (Node _ t0 t1) = 1 + (size t0) + (size t1)
>
>
>
> from_list :: (Ord t) => [t] -> Heap t
> from_list = foldr insert empty
>
> to_list   :: (Ord t) => Heap t -> [t]
> to_list   = unfoldr (\h -> if is_empty h then Nothing else Just (get_max
> h, delete_max h))
>
> heap_sort :: (Ord t) => [t] -> [t]
> heap_sort = to_list . from_list
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070519/ada88b5d/attachment-0001.htm