BINOMIAL HEAPS
From Okasaky, "Pure Functional Data Structures", Ch.3

> module Binomial_Heaps where

> import Leftist_Heaps (Heap (..),
>                       heapList,
>                       listHeap,
>                       lHeapSort)

Binomial Trees

> data BTree a = Node Int a [BTree a]
>   deriving (Eq,Show)

The integer argument is the rank.

> rank :: BTree a -> Int
> rank (Node r _ _) = r

> root :: BTree a -> a
> root (Node _ x _) = x

Binomial trees should have the following structure:
A binomial tree of rank 0 is a single node with empty list of children;
A binomial tree of rank (n+1) is a node with a list of children of ranks
   n, n-1, n-2, ..., 0

Linking two binomial trees of same rank.
Assuming that they are heap ordered, the result is also heap ordered

> link :: Ord a => BTree a -> BTree a -> BTree a
> link t1@(Node r x1 c1) t2@(Node _ x2 c2)
>   | x1<=x2    = Node (r+1) x1 (t2:c1)
>   | otherwise = Node (r+1) x2 (t1:c2)

A binomial tree of rank r contains 2^r elements.

A binomial heap is a list of binomial trees of strictly increasing rank.
                
> type BHeap a = [BTree a]

The separation of elements into trees in a heap is similar to
the representation of a natural number in binary form.
As a number can be written as a sum of powers of two,
a heap can be written as a list of binomial trees.

Inserting a tree into a heap.
We assume that the rank of the tree is smaller or equal
to the rank of the components of the heap

> insTree :: Ord a => BTree a -> BHeap a -> BHeap a
> insTree t [] = [t]
> insTree t ts@(t':ts')
>   | rank t < rank t' = t:ts
>   | otherwise        = insTree (link t t') ts'

insTree is analogous to the the propagation of a "carry" in binary arithmetic.

> insertB :: Ord a => a -> BHeap a -> BHeap a
> insertB x ts = insTree (Node 0 x []) ts

Merging is analogous to addition of binary numbers.

> mergeB :: Ord a => BHeap a -> BHeap a -> BHeap a
> mergeB []  ts2 = ts2
> mergeB ts1 []  = ts1
> mergeB ts1@(t1:ts1') ts2@(t2:ts2')
>   | rank t1 < rank t2 = t1 : mergeB ts1' ts2
>   | rank t2 < rank t1 = t2 : mergeB ts1 ts2'
>   | otherwise         = insTree (link t1 t2) (mergeB ts1' ts2')

removeMinTree looks for the minimum element and extracts the trees
where it is from the heap.

> removeMinTree :: Ord a => BHeap a -> (BTree a, BHeap a)
> removeMinTree [t] = (t,[])
> removeMinTree (t:ts)
>   | root t < root t' = (t,ts)
>   | otherwise        = (t', t:ts')
>   where (t',ts') = removeMinTree ts

The minimum is just the root of the removed tree.

> findBMin :: Ord a => BHeap a -> a
> findBMin = root . fst . removeMinTree

When removing the minimum, we must put back the list of subtrees of the
extracted tree into the heap.
In the tree, the elements are in decreasing order of rank,
while in a heap they must be in increasing order;
therefore we must reverse the list before merging.

> deleteBMin :: Ord a => BHeap a -> BHeap a
> deleteBMin ts = let (Node _ _ ts1, ts2) = removeMinTree ts
>                 in  mergeB (reverse ts1) ts2

COMPLEXITY: all heap operations take O(log n) time.

Exercise:
Define an instance of the Heap type class (from the Leftist Heap file)
for binomial heaps.
Using to realise a sorting function that uses binomial heaps.

We can't define an instance of Heap directly for BHeap
because (BHeap a) is a type synonym for [BTree a]:
we can define instances only for "new types".
By "new types" we mean those defined by the "data" and "newtype" declarations.

So we define a new type that is identical to BHeap
but just has a wrapping constructor around it.

> newtype BinHeap a = BinHeap (BHeap a)

> instance Heap BinHeap where
>   empty = BinHeap []
>   isEmpty (BinHeap h) = h==[] 
>   insert a (BinHeap h) = BinHeap $ insertB a h
>   merge (BinHeap h1) (BinHeap h2) = BinHeap (mergeB h1 h2)
>   findMin (BinHeap h) = findBMin h
>   deleteMin (BinHeap h) = BinHeap $ deleteBMin h

Sorting with binomial heaps is then exactly the same as sorting
with leftist heaps, we just specify a different type for the
intermediate data structure.

> binSort :: Ord a => [a] -> [a]
> binSort = heapList . (listHeap :: Ord a => [a]-> BinHeap a)