llrbtree-0.1.0: Purely functional data structure

Data.Heap.Leftist

Description

Leftist Heap

• the fun of programming

Synopsis

# Data structures

data Leftist a Source

Constructors

 Leaf Node Rank (Leftist a) a (Leftist a)

Instances

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

# Creating heaps

Empty heap.

singleton :: a -> Leftist aSource

Singleton heap.

insert :: Ord a => a -> Leftist a -> Leftist aSource

Insertion.

````>>> ````insert 7 (fromList [5,3]) == fromList [3,5,7]
```True
`>>> ````insert 5 empty            == singleton 5
```True
```

fromList :: Ord a => [a] -> Leftist 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 :: Leftist 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 => Leftist a -> Leftist aSource

Deleting the minimum element.

````>>> ````deleteMin (fromList [5,3,7]) == fromList [5,7]
```True
`>>> ````deleteMin empty == empty
```True
```

# Checking heaps

null :: Leftist t -> BoolSource

See if the heap is empty.

````>>> ````Data.Heap.Leftist.null empty
```True
`>>> ````Data.Heap.Leftist.null (singleton 1)
```False
```

# Helper functions

merge :: Ord a => Leftist a -> Leftist a -> Leftist aSource

Merging two heaps

````>>> ````merge (fromList [5,3]) (fromList [5,7]) == fromList [3,5,5,7]
```True
```

minimum :: Leftist a -> Maybe aSource

Finding the minimum element.

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

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

Checking validity of a heap.

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