llrbtree-0.1.1: Purely functional sets and heaps

Data.Heap.Skew

Description

Skew Heap

• the fun of programming

Synopsis

# Data structures

data Skew a Source

Constructors

 Leaf Node (Skew a) a (Skew a)

Instances

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

# Creating heaps

Empty heap.

singleton :: a -> Skew aSource

Singleton heap.

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

Insertion.

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

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

Deleting the minimum element.

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

# Checking heaps

null :: Skew t -> BoolSource

See if the heap is empty.

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

# Helper functions

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

Merging two heaps

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

minimum :: Skew a -> Maybe aSource

Finding the minimum element.

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

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

Checking validity of a heap.

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