Binominal Heap
- the fun of programming
- newtype Heap a = Heap [Tree a]
- data Tree a = Node Rank a [Tree a]
- type Rank = Int
- empty :: Heap a
- singleton :: a -> Heap a
- insert :: Ord a => a -> Heap a -> Heap a
- fromList :: Ord a => [a] -> Heap a
- toList :: Heap a -> [a]
- deleteMin :: Ord a => Heap a -> Heap a
- null :: Heap a -> Bool
- merge :: Ord a => Heap a -> Heap a -> Heap a
- minimum :: Ord a => Heap a -> Maybe a
- valid :: Ord a => Heap a -> Bool
- heapSort :: Ord a => Heap a -> [a]
Data structures
Creating heaps
insert :: Ord a => a -> Heap a -> Heap aSource
Insertion.
>>>
insert 7 (fromList [5,3]) == fromList [3,5,7]
True>>>
insert 5 empty == singleton 5
True
fromList :: Ord a => [a] -> Heap aSource
Creating a heap from a list.
>>>
empty == fromList []
True>>>
singleton 'a' == fromList ['a']
True>>>
fromList [5,3] == fromList [5,3]
True
Converting to a list
Creating a list from a heap. O(N)
>>>
let xs = [5,3,5]
>>>
length (toList (fromList xs)) == length xs
True>>>
toList empty
[]
Deleting
deleteMin :: Ord a => Heap a -> Heap aSource
Deleting the minimum element.
>>>
deleteMin (fromList [5,3,7]) == fromList [5,7]
True>>>
deleteMin empty == empty
True
Checking heaps
See if the heap is empty.
>>>
Data.Heap.Binominal.null empty
True>>>
Data.Heap.Binominal.null (singleton 1)
False
Helper functions
merge :: Ord a => Heap a -> Heap a -> Heap aSource
Merging two heaps
>>>
merge (fromList [5,3]) (fromList [5,7]) == fromList [3,5,5,7]
True