EdisonCore-1.2.1: A library of efficient, purely-functional data structures (Core Implementations)ContentsIndex
Data.Edison.Coll.SplayHeap
PortabilityGHC, Hugs (MPTC and FD)
Stabilitystable
Maintainerrobdockins AT fastmail DOT fm
Contents
Type of splay heaps
CollX operations
Coll operations
OrdCollX operations
OrdColl operations
Documentation
Description

Splay heaps.

If minElem is called frequently, then SplayHeap should be used in conjunction with Data.Edison.Coll.MinHeap.

References:

  • Chris Okasaki. Purely Functional Data Structures. 1998. Section 5.4.
Synopsis
data Heap a
empty :: Heap a
singleton :: a -> Heap a
fromSeq :: (Ord a, Sequence s) => s a -> Heap a
insert :: Ord a => a -> Heap a -> Heap a
insertSeq :: (Ord a, Sequence s) => s a -> Heap a -> Heap a
union :: Ord a => Heap a -> Heap a -> Heap a
unionSeq :: (Ord a, Sequence s) => s (Heap a) -> Heap a
delete :: Ord a => a -> Heap a -> Heap a
deleteAll :: Ord a => a -> Heap a -> Heap a
deleteSeq :: (Ord a, Sequence s) => s a -> Heap a -> Heap a
null :: Heap a -> Bool
size :: Heap a -> Int
member :: Ord a => a -> Heap a -> Bool
count :: Ord a => a -> Heap a -> Int
strict :: Heap a -> Heap a
structuralInvariant :: Ord a => Heap a -> Bool
toSeq :: (Ord a, Sequence s) => Heap a -> s a
lookup :: Ord a => a -> Heap a -> a
lookupM :: (Ord a, Monad m) => a -> Heap a -> m a
lookupAll :: (Ord a, Sequence s) => a -> Heap a -> s a
lookupWithDefault :: Ord a => a -> a -> Heap a -> a
fold :: Ord a => (a -> b -> b) -> b -> Heap a -> b
fold' :: Ord a => (a -> b -> b) -> b -> Heap a -> b
fold1 :: Ord a => (a -> a -> a) -> Heap a -> a
fold1' :: Ord a => (a -> a -> a) -> Heap a -> a
filter :: Ord a => (a -> Bool) -> Heap a -> Heap a
partition :: Ord a => (a -> Bool) -> Heap a -> (Heap a, Heap a)
strictWith :: (a -> b) -> Heap a -> Heap a
deleteMin :: Ord a => Heap a -> Heap a
deleteMax :: Ord a => Heap a -> Heap a
unsafeInsertMin :: Ord a => a -> Heap a -> Heap a
unsafeInsertMax :: Ord a => a -> Heap a -> Heap a
unsafeFromOrdSeq :: (Ord a, Sequence s) => s a -> Heap a
unsafeAppend :: Ord a => Heap a -> Heap a -> Heap a
filterLT :: Ord a => a -> Heap a -> Heap a
filterLE :: Ord a => a -> Heap a -> Heap a
filterGT :: Ord a => a -> Heap a -> Heap a
filterGE :: Ord a => a -> Heap a -> Heap a
partitionLT_GE :: Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLE_GT :: Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GT :: Ord a => a -> Heap a -> (Heap a, Heap a)
minView :: (Ord a, Monad m) => Heap a -> m (a, Heap a)
minElem :: Ord a => Heap a -> a
maxView :: (Ord a, Monad m) => Heap a -> m (a, Heap a)
maxElem :: Ord a => Heap a -> a
foldr :: Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr' :: Ord a => (a -> b -> b) -> b -> Heap a -> b
foldl :: Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl' :: Ord a => (b -> a -> b) -> b -> Heap a -> b
foldr1 :: Ord a => (a -> a -> a) -> Heap a -> a
foldr1' :: Ord a => (a -> a -> a) -> Heap a -> a
foldl1 :: Ord a => (a -> a -> a) -> Heap a -> a
foldl1' :: Ord a => (a -> a -> a) -> Heap a -> a
toOrdSeq :: (Ord a, Sequence s) => Heap a -> s a
unsafeMapMonotonic :: (a -> b) -> Heap a -> Heap b
Type of splay heaps
data Heap a
show/hide Instances
(Ord a, Arbitrary a) => Arbitrary (Heap a)
Ord a => Eq (Heap a)
Ord a => Monoid (Heap a)
Ord a => Ord (Heap a)
(Ord a, Read a) => Read (Heap a)
(Ord a, Show a) => Show (Heap a)
Ord a => Coll (Heap a) a
Ord a => CollX (Heap a) a
Ord a => OrdColl (Heap a) a
Ord a => OrdCollX (Heap a) a
CollX operations
empty :: Heap a
singleton :: a -> Heap a
fromSeq :: (Ord a, Sequence s) => s a -> Heap a
insert :: Ord a => a -> Heap a -> Heap a
insertSeq :: (Ord a, Sequence s) => s a -> Heap a -> Heap a
union :: Ord a => Heap a -> Heap a -> Heap a
unionSeq :: (Ord a, Sequence s) => s (Heap a) -> Heap a
delete :: Ord a => a -> Heap a -> Heap a
deleteAll :: Ord a => a -> Heap a -> Heap a
deleteSeq :: (Ord a, Sequence s) => s a -> Heap a -> Heap a
null :: Heap a -> Bool
size :: Heap a -> Int
member :: Ord a => a -> Heap a -> Bool
count :: Ord a => a -> Heap a -> Int
strict :: Heap a -> Heap a
structuralInvariant :: Ord a => Heap a -> Bool
Coll operations
toSeq :: (Ord a, Sequence s) => Heap a -> s a
lookup :: Ord a => a -> Heap a -> a
lookupM :: (Ord a, Monad m) => a -> Heap a -> m a
lookupAll :: (Ord a, Sequence s) => a -> Heap a -> s a
lookupWithDefault :: Ord a => a -> a -> Heap a -> a
fold :: Ord a => (a -> b -> b) -> b -> Heap a -> b
fold' :: Ord a => (a -> b -> b) -> b -> Heap a -> b
fold1 :: Ord a => (a -> a -> a) -> Heap a -> a
fold1' :: Ord a => (a -> a -> a) -> Heap a -> a
filter :: Ord a => (a -> Bool) -> Heap a -> Heap a
partition :: Ord a => (a -> Bool) -> Heap a -> (Heap a, Heap a)
strictWith :: (a -> b) -> Heap a -> Heap a
OrdCollX operations
deleteMin :: Ord a => Heap a -> Heap a
deleteMax :: Ord a => Heap a -> Heap a
unsafeInsertMin :: Ord a => a -> Heap a -> Heap a
unsafeInsertMax :: Ord a => a -> Heap a -> Heap a
unsafeFromOrdSeq :: (Ord a, Sequence s) => s a -> Heap a
unsafeAppend :: Ord a => Heap a -> Heap a -> Heap a
filterLT :: Ord a => a -> Heap a -> Heap a
filterLE :: Ord a => a -> Heap a -> Heap a
filterGT :: Ord a => a -> Heap a -> Heap a
filterGE :: Ord a => a -> Heap a -> Heap a
partitionLT_GE :: Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLE_GT :: Ord a => a -> Heap a -> (Heap a, Heap a)
partitionLT_GT :: Ord a => a -> Heap a -> (Heap a, Heap a)
OrdColl operations
minView :: (Ord a, Monad m) => Heap a -> m (a, Heap a)
minElem :: Ord a => Heap a -> a
maxView :: (Ord a, Monad m) => Heap a -> m (a, Heap a)
maxElem :: Ord a => Heap a -> a
foldr :: Ord a => (a -> b -> b) -> b -> Heap a -> b
foldr' :: Ord a => (a -> b -> b) -> b -> Heap a -> b
foldl :: Ord a => (b -> a -> b) -> b -> Heap a -> b
foldl' :: Ord a => (b -> a -> b) -> b -> Heap a -> b
foldr1 :: Ord a => (a -> a -> a) -> Heap a -> a
foldr1' :: Ord a => (a -> a -> a) -> Heap a -> a
foldl1 :: Ord a => (a -> a -> a) -> Heap a -> a
foldl1' :: Ord a => (a -> a -> a) -> Heap a -> a
toOrdSeq :: (Ord a, Sequence s) => Heap a -> s a
unsafeMapMonotonic :: (a -> b) -> Heap a -> Heap b
Documentation
Produced by Haddock version 0.8