CODEWITHSUNDEEP
haskell
Yamahiou
Yamahiou

Reputation: 11

Binomial Heap implementation in Haskell

I'm trying to implement a Binomial Heap in Haskell, using the book "Purely Functional Data Structures" Chris Okasaki. 

{- Implemetation of Binomial Heap-}
module BinomialHeap where

 {- Definition of a Binomial Tree -}
 data BTree a = Node Int a ([BTree a]) deriving Show

 {- Definition of a Binomial Heap -}
 data BHeap a = Heap [BTree a] deriving Show

 empty :: BHeap a
 empty = Heap []


 {- Linking function tree -}
    -- w/ larger root is
    --  linked w/ tree w/ lower root  -}
 link :: Ord a => BTree a -> BTree a -> BTree a
 link t1@(Node r x1 c1) t2@(Node _ x2 c2) =
    if x1 < x2 then
        Node (r+1) x1 (t2:c1)
    else
        Node (r+1) x2 (t1:c2)

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

 {- Gives the rank of the Binomial Tree-} 
 rank :: BTree a -> Int 
 rank (Node r _ _ ) = r

 {- Insertion in the tree -}
    -- Create a new singl. tree
    -- Step through the existing trees in increasing order
    -- until we find a missing rank
    -- link tree of equal ranks
    -- atm it's O(log n)
 insTree :: Ord a => BTree a -> [BTree a] -> [BTree a]
 insTree t [] = [t]
 insTree t ts1@(t1':ts1') =
     if rank t > rank t1' then
        t:ts1
     else
        insTree (link t t1') ts1'

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

 {- Merge of Heaps-}
    --  We step through both list of tree in increasing order
    -- link tree of equal root
 merge :: Ord a => [BTree a] -> [BTree a] -> [BTree a]
 merge [] ts = ts 
 merge ts [] = ts
 merge ts1@(t1:ts1') ts2@(t2:ts2') = 
    if rank t1 < rank t2 then
        t1:merge ts1' ts2
    else if rank t2 < rank t1 then
        t2:merge ts1 ts2'
    else 
        insTree (link t1 t2) (merge ts1' ts2')


 sampleHeap :: BHeap Int
 sampleHeap = foldl insert empty [1, 2, 3]

The problem is that insertion gives me an output that isn't right :

Heap [Node 1 1 [Node 0 3 [],Node 0 2 []]]

The insertion primitive might not be correct. Okasaki says :

"To insert a new element into a heap, we first create a new singleton tree (rank 0). We then step through the existing trees in increasing order of rank until we find a missing rank, linking tree of equal rank as we go. Each link corresponds to a carry in binary arithmetic"

Can you help me find where there can be an error in the insertions primitives ? Thank you.

Upvotes: 1

Views: 1162

Answers (1)

Kartik Sabharwal
Kartik Sabharwal

Reputation: 503

From page 71 of Okasaki's paper (https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf):

For reasons that will become clear later, we maintain the list of trees representing a heap in increasing order of rank, but maintain the list of trees representing the children of a node in decreasing order of rank.

Let's look at your insTree function in light of this statement:

 insTree :: Ord a => BTree a -> [BTree a] -> [BTree a]
 insTree t [] = [t]
 insTree t ts1@(t1':ts1') =
     if rank t > rank t1' then
        t:ts1
     else
        insTree (link t t1') ts1'

Pay attention to the case where the list of binomial trees isn't empty. The code there says if the rank of the tree being inserted is greater than the rank of next tree in the list, prepend the tree to the list. This violates the assumption that the list of trees representing a heap is organized in increasing order of rank. Reversing the sign from > to < in the comparison should fix the problem.

Upvotes: 2

Related Questions