llrbtree-0.1.1: Purely functional sets and heaps

Data.Heap.Binominal

Description

Binominal Heap

• the fun of programming

Synopsis

# Data structures

newtype Heap a Source

Constructors

 Heap [Tree a]

Instances

 (Eq a, Ord a) => Eq (Heap a) Show a => Show (Heap a)

data Tree a Source

Constructors

 Node Rank a [Tree a] Rank, a minimum root element, trees

Instances

 Show a => Show (Tree a)

# Creating heaps

Empty heap.

singleton :: a -> Heap aSource

Singleton heap.

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

toList :: Heap a -> [a]Source

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

null :: Heap a -> BoolSource

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
```

minimum :: Ord a => Heap a -> Maybe aSource

Finding the minimum element.

````>>> ````minimum (fromList [3,5,1])
```Just 1
`>>> ````minimum empty
```Nothing
```

valid :: Ord a => Heap a -> BoolSource

Checking validity of a heap.

heapSort :: Ord a => Heap a -> [a]Source