Invisible wrote:

> [For anybody not already familiar with such things...
> 
> A Min Heap is a kind of binary tree that stores data in such a way that 
> retrieving the "minimum" element is an O(1) operation. Insertion and 
> deletion are both O(log n), and I believe joining two heaps should be 
> O(log n) as well.

data MinHeap x = Node x (MinHeap x) (MinHeap x) | Null

is_empty Null = True
is_empty _    = False

top (Null) = error "empty heap"
top (Node x _ _) = x

insert nx (Null) = Node x Null Null
insert nx (Node x h0 h1) = Node (min x nx) (insert (max x nx) h1) h0

delete (Null) = error "empty heap"
delete (Node _ h0 Null) = h0
delete (Node _ Null h1) = h1
delete (Node _ h0 h1) =
   let x0 = top h0; x1 = top h1
   in  if x0 < x1
         then Node x0 (delete h0) h1
         else Node x1 (delete h1) h0

> A "heap sort" involves turning something into a heap (with O(n log n) 
> complexity) and then repeatedly removing the minimum element (with O(n) 
> complexity) to yield a fully sorted list.

list_to_heap = foldl' insert Null

heap_to_list = unfoldr (\h -> if is_empty h then Nothing else (top h, 
delete h))

heap_sort = heap_to_list . list_to_heap

> To build a "Huffman tree", you start with a set of trivial 1-node trees. 
> Each tree has a probability assigned to it. The algorithm is to simply 
> select the two lowest-probability tries, remove them from the set, 
> combine them into a larger tree (with a correspondingly higher 
> probability) and insert this back into the set. Eventually you will have 
> 1 tree with Pr=1.

data Tree x =
   Leaf   {prob :: Double, symbol :: x} |
   Branch {prob :: Double, branch0, branch1 :: Tree x}

instance Eq (Tree x) where
   x == y   =   prob x == prob y

instance Ord (Tree x) where
   compare x y = compare (prob x) (prob y)

huffman :: (Ord x) => [(x,Double)] -> Tree x
huffman = top . build . setup
   where
     setup :: (Ord x) => [(x,Double)] -> MinHeap (Tree x)
     setup = list_to_heap . map (\(x,pr) -> Leaf {prob = pr, symbol = x})

     build :: (Ord x) => MinHeap (Tree x) -> Tree x
     build (Node t Null Null) = t
     build h =
       let
         (t0,h0) = (top h,  delete h)
         (t1,h1) = (top h0, delete h0)
       in insert (make_branch t0 t1) h1

     make_branch t0 t1 =
      Branch {prob = prob t0 + prob t1, branch0 = t0, branch1 = t1}

> Here ends the lesson on algorithms and data structures.]

[You knew it had to be done...]

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message