Data.Edison.Coll.SplayHeap
 Portability GHC, Hugs (MPTC and FD) Stability stable Maintainer robdockins 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
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