Sorting algorithms/Heapsort: Difference between revisions
→{{header|Haskell}}: add an implementation using only the standard library
(→{{header|Pascal}}: replaced incorrect previous version) |
Corpsmoderne (talk | contribs) (→{{header|Haskell}}: add an implementation using only the standard library) |
||
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 ⟶ 2,974:
where (x,r) = (findMin h,deleteMin h)
e.g.
<syntaxhighlight lang="haskell">*Main> heapsort [[6,9],[2,13],[6,8,14,9],[10,7],[5]]
| |||