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
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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe