Skip to content

Instantly share code, notes, and snippets.

@mmagm
Last active February 2, 2018 07:21
Show Gist options
  • Save mmagm/2694665 to your computer and use it in GitHub Desktop.
Save mmagm/2694665 to your computer and use it in GitHub Desktop.
haskell heap sort
import Data.List
swap :: Int -> Int -> [a] -> [a]
swap i j xs | i == j = xs
swap i j xs | otherwise = initial ++ (xs !! b) : middle ++ (xs !! a) : end
where [a,b] = sort [i,j]
initial = take a xs
middle = take (b-a-1) (drop (a+1) xs)
end = drop (b+1) xs
largest :: Ord a => Int -> Int -> [a] -> Int
largest i hs xs =
let large = if (l < hs) && ((xs !! l) > (xs !! i)) then l else i
in if (r < hs) && ((xs !! r) > (xs !! large)) then r else large
where l = 2 * i + 1
r = 2 * i + 2
heapify :: Ord a => Int -> Int -> [a] -> [a]
heapify i hs xs =
if (large /= i) then heapify large hs (swap large i xs)
else xs
where large = largest i hs xs
buildheap :: Ord a => Int -> [a] -> [a]
buildheap 0 xs = heapify 0 (length xs) xs
buildheap i xs = buildheap (i - 1) (heapify i (length xs) xs)
hpsort i xs = let swapped = swap 0 i xs
in if i /= 1 then hpsort (i - 1) (heapify 0 i swapped)
else (heapify 0 i swapped)
heapsort xs = let heap = buildheap (length xs `div` 2) xs
in heapsorting (length xs - 1) heap
-- heapsort [16,4,10,14,7,9,3,2,8]
@vlastachu
Copy link

Hi. Nice code! I am reading "Introduction to Algorithms" and trying to write algorithms on haskell. I reached to heapsort and got a troubles. It is very imperative. So I wanted to say: your decision is done correctly according to the algorithm, but it is not effective. You know swap, take, drop, ++ it is all works for O(n). heapsort ([1..10000]):
"sample.hs: out of memory
[Finished in 138.6s with exit code 1]"

possible solutions

  1. read Okasaki's Purely Functional Data Structures (advice from SO)
  2. use ST Array monad.
  3. realise heap as tree, not list. It's wrong but it's easier and clearer and faster.
    I'll try 3d
    PS Also on 33 line heapsorting -> hpsort

@isopropylcyanide
Copy link

Yes, the array immutability makes it almost infeasible for a direct algorithm such as this to work. I read some of Chris Okasaki's work and I must confess it got me. Anyway, nice code indeed. There are some redundant guards though.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment