Data.Heap.Splay

Purely functional top-down splay heaps.

• D.D. Sleator and R.E. Rarjan, "Self-Adjusting Binary Search Tree", Journal of the Association for Computing Machinery, Vol 32, No 3, July 1985, pp 652-686. http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf

Data structures

data Heap a

Constructors

None

Some a (Splay a)

Instances

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

Show a => Show (Heap a)

data Splay a

Constructors

Leaf

Node (Splay a) a (Splay a)

Instances

Show a => Show (Splay a)

Creating heaps

empty :: Heap a

Empty heap.

singleton :: a -> Heap a

Singleton heap.

insert :: Ord a => a -> Heap a -> Heap a

Insertion.

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

fromList :: Ord a => [a] -> Heap a

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]

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 a

Deleting the minimum element.

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

Checking heaps

null :: Heap a -> Bool

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)

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 a

Merging two heaps

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

minimum :: Heap a -> Maybe a

Finding the minimum element.

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

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

Checking validity of a heap.

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

showHeap :: Show a => Splay a -> String

printHeap :: Show a => Splay a -> IO ()