Sorting algorithms/Heapsort: Difference between revisions

Content added Content deleted

Inline

@@ Line 2,926: / Line 2,926: @@
 =={{header|Haskell}}==
+<syntaxhighlight lang="haskell">data Tree a = Nil
+            | Node a (Tree a) (Tree a)
+            deriving Show
+insert :: Ord a => a -> Tree a -> Tree a
+insert x Nil = Node x Nil Nil
+insert x (Node y leftBranch rightBranch)
+  | x < y = Node x (insert y rightBranch) leftBranch
+  | otherwise = Node y (insert x rightBranch) leftBranch
+merge :: Ord a => Tree a -> Tree a -> Tree a
+merge Nil t = t
+merge t Nil = t
+merge tx@(Node vx lx rx) ty@(Node vy ly ry)
+  | vx < vy = Node vx (merge lx rx) ty
+  | otherwise = Node vy tx (merge ly ry)
+fromList :: Ord a => [a] -> Tree a
+fromList = foldr insert Nil
+toList :: Ord a => Tree a -> [a]
+toList Nil = []
+toList (Node x l r) = x : toList (merge l r)
+mergeSort :: Ord a => [a] -> [a]
+mergeSort = toList . fromList</syntaxhighlight>
+e.g
+<syntaxhighlight lang="haskell">ghci> heapSort [9,5,8,2,1,4,6,3,0,7]
+[0,1,2,3,4,5,6,7,8,9]
+</syntaxhighlight>
 Using package [http://hackage.haskell.org/package/fgl fgl] from HackageDB
 <syntaxhighlight lang="haskell">import Data.Graph.Inductive.Internal.Heap(
@@ Line 2,940: / Line 2,974: @@
            where (x,r) = (findMin h,deleteMin h)
-heapsort :: Ord a => [a] -> [a]
+heapSort :: Ord a => [a] -> [a]
-heapsort = (map fst) . toList . build . map (\x->(x,x))</syntaxhighlight>
+heapSort = (map fst) . toList . build . map (\x->(x,x))</syntaxhighlight>
 e.g.
 <syntaxhighlight lang="haskell">*Main> heapsort [[6,9],[2,13],[6,8,14,9],[10,7],[5]]