I think (although I am far from an expert) that it is a skew heap, based on this: http://<font size="-1"><span class="a"><a href="http://www.palgrave.com/pdfs/0333992857.pdf">www.palgrave.com/pdfs/0333992857.pdf</a></span>
</font><br><br><div><span class="gmail_quote">On 19/05/07, <b class="gmail_sendername">Andrew Coppin</b> <<a href="mailto:andrewcoppin@btinternet.com">andrewcoppin@btinternet.com</a>> wrote:</span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Greetings.<br><br>I have just implemented a heap. But... um... I can't acutally figure out<br>*which kind* of heap it is! LOL. Any ideas?<br><br>(Seems to work really well, whatever it is. Oh, and I discovered that<br>
you can sort data just by shoving it all into a heap, and then taking it<br>all out again. Apparently this is a standard algorithm, and it's known<br>as a "heap sort", unsurprisingly. You learn something every day...)
<br><br><br>module Heap where<br><br>import Data.List (intersperse, unfoldr)<br><br>data Heap t = Node !t !(Heap t) !(Heap t) | Null<br><br>instance (Show t) => Show (Heap t) where<br> show = work "" where<br>
work p (Null) = p ++ "-"<br> work p (Node v t0 t1) = concat $ intersperse "\n" $ [work (' ':p)<br>t0, p ++ show v, work (' ':p) t1]<br><br>empty = Null<br><br>is_empty Null = True
<br>is_empty _ = False<br><br>insert v (Null) = Node v Null Null<br>insert v (Node v0 t0 t1) =<br> let lo = min v v0<br> hi = max v v0<br> in Node hi (insert lo t1) t0<br><br>get_max (Null) = error "heap is empty"
<br>get_max (Node v _ _) = v<br><br>delete_max (Null) = error "heap is empty"<br>delete_max (Node _ Null Null) = Null<br>delete_max (Node _ Null t1) = t1<br>delete_max (Node _ t0 Null) = t0<br>delete_max (Node _ t0 t1)
<br> | get_max t0 > get_max t1 = Node (get_max t0) (delete_max t0) t1<br> | otherwise = Node (get_max t1) t0<br>(delete_max t1)<br><br>size (Null) = 0<br>size (Node _ t0 t1) = 1 + (size t0) + (size t1)
<br><br><br><br>from_list :: (Ord t) => [t] -> Heap t<br>from_list = foldr insert empty<br><br>to_list :: (Ord t) => Heap t -> [t]<br>to_list = unfoldr (\h -> if is_empty h then Nothing else Just (get_max
<br>h, delete_max h))<br><br>heap_sort :: (Ord t) => [t] -> [t]<br>heap_sort = to_list . from_list<br><br>_______________________________________________<br>Haskell-Cafe mailing list<br><a href="mailto:Haskell-Cafe@haskell.org">
Haskell-Cafe@haskell.org</a><br><a href="http://www.haskell.org/mailman/listinfo/haskell-cafe">http://www.haskell.org/mailman/listinfo/haskell-cafe</a><br></blockquote></div><br>