Leftist Heap

- the fun of programming

- data Leftist a
- type Rank = Int
- empty :: Leftist a
- singleton :: a -> Leftist a
- insert :: Ord a => a -> Leftist a -> Leftist a
- fromList :: Ord a => [a] -> Leftist a
- toList :: Leftist a -> [a]
- deleteMin :: Ord a => Leftist a -> Leftist a
- null :: Leftist t -> Bool
- merge :: Ord a => Leftist a -> Leftist a -> Leftist a
- minimum :: Leftist a -> Maybe a
- valid :: Ord a => Leftist a -> Bool
- heapSort :: Ord a => Leftist a -> [a]

# Data structures

# Creating heaps

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

Insertion.

`>>>`

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

`>>>`

True`insert 5 empty == singleton 5`

fromList :: Ord a => [a] -> Leftist aSource

Creating a heap from a list.

`>>>`

True`empty == fromList []`

`>>>`

True`singleton 'a' == fromList ['a']`

`>>>`

True`fromList [5,3] == fromList [5,3]`

# Converting to a list

toList :: Leftist a -> [a]Source

Creating a list from a heap. O(N)

`>>>`

`let xs = [5,3,5]`

`>>>`

True`length (toList (fromList xs)) == length xs`

`>>>`

[]`toList empty`

# Deleting

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

Deleting the minimum element.

`>>>`

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

`>>>`

True`deleteMin empty == empty`

# Checking heaps

null :: Leftist t -> BoolSource

See if the heap is empty.

`>>>`

True`Data.Heap.Leftist.null empty`

`>>>`

False`Data.Heap.Leftist.null (singleton 1)`

# Helper functions

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

Merging two heaps

`>>>`

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