llrbtree-0.1.1: Purely functional sets and heaps

Data.Heap.Splay

Description

Purely functional top-down splay heaps.

Synopsis

Data structures

data Heap a Source

Constructors

 None Some a (Splay a)

Instances

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

data Splay a Source

Constructors

 Leaf Node (Splay a) a (Splay a)

Instances

 Show a => Show (Splay 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 :: 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.Splay.null empty
```True
`>>> ````Data.Heap.Splay.null (singleton 1)
```False
```

Helper functions

partition :: Ord a => a -> Splay a -> (Splay a, Splay a)Source

Splitting smaller and bigger with splay. Since this is a heap implementation, members is not necessarily unique.

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