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 Heap a
- data Splay a
- empty :: Heap a
- singleton :: a -> Heap a
- insert :: Ord a => a -> Heap a -> Heap a
- fromList :: Ord a => [a] -> Heap a
- toList :: Heap a -> [a]
- deleteMin :: Heap a -> Heap a
- null :: Heap a -> Bool
- partition :: Ord a => a -> Splay a -> (Splay a, Splay a)
- merge :: Ord a => Heap a -> Heap a -> Heap a
- minimum :: Heap a -> Maybe a
- valid :: Ord a => Heap a -> Bool
- heapSort :: Ord a => Heap a -> [a]
- showHeap :: Show a => Splay a -> String
- printHeap :: Show a => Splay a -> IO ()
insert 7 (fromList [5,3]) == fromList [3,5,7]True
insert 5 empty == singleton 5True
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
Creating a list from a heap. O(N)
let xs = [5,3,5]
length (toList (fromList xs)) == length xsTrue
Deleting the minimum element.
deleteMin (fromList [5,3,7]) == fromList [5,7]True
deleteMin empty == emptyTrue
See if the heap is empty.
Data.Heap.Splay.null (singleton 1)False
Splitting smaller and bigger with splay. Since this is a heap implementation, members is not necessarily unique.
Merging two heaps
merge (fromList [5,3]) (fromList [5,7]) == fromList [3,5,5,7]True
Finding the minimum element.
minimum (fromList [3,5,1])Just 1