heapsort :: Ord a => [a] -> [a]
heapsort xs = decomposetree (composetree xs)
data Tree a = Leaf | Node (Tree a) a (Tree a)
composetree :: Ord a => [a] -> Tree a
composetree xs =
case xs of
[] -> Leaf
y : ys -> insert y (composetree ys)
insert :: Ord a => a -> Tree a -> Tree a
insert x t =
case t of
Leaf -> Node Leaf x Leaf
Node l e r -> if e <= x then Node (insert x r) e l
else Node (insert e r) x l
decomposetree :: Ord a => Tree a -> [a]
decomposetree t =
case t of
Leaf -> []
Node l e r -> e : decomposetree (removemin (Node l e r))
removemin :: Ord a => Tree a -> Tree a
removemin t =
case t of
Leaf -> Leaf
Node l e r ->
case l of
Leaf -> r
Node l1 e1 r1 ->
case r of
Leaf -> Node l1 e1 r1
Node l2 e2 r2 ->
if e1 <= e2 then Node (removemin (Node l1 e1 r1)) e1 (Node l2 e2 r2)
else Node (Node l1 e1 r1) e2 (removemin (Node l2 e2 r2))