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 moduleName :: String
Type of splay heaps
 data Heap a Source
Instances
 Ord a => Eq (Heap a) Ord a => Ord (Heap a) (Ord a, Read a) => Read (Heap a) (Ord a, Show a) => Show (Heap a) Ord a => Monoid (Heap a) (Ord a, Arbitrary a) => Arbitrary (Heap a) Ord a => CollX (Heap a) a Ord a => OrdCollX (Heap a) a Ord a => Coll (Heap a) a Ord a => OrdColl (Heap a) a
CollX operations
 empty :: Heap a Source
 singleton :: a -> Heap a Source
 fromSeq :: (Ord a, Sequence s) => s a -> Heap a Source
 insert :: Ord a => a -> Heap a -> Heap a Source
 insertSeq :: (Ord a, Sequence s) => s a -> Heap a -> Heap a Source
 union :: Ord a => Heap a -> Heap a -> Heap a Source
 unionSeq :: (Ord a, Sequence s) => s (Heap a) -> Heap a Source
 delete :: Ord a => a -> Heap a -> Heap a Source
 deleteAll :: Ord a => a -> Heap a -> Heap a Source
 deleteSeq :: (Ord a, Sequence s) => s a -> Heap a -> Heap a Source
 null :: Heap a -> Bool Source
 size :: Heap a -> Int Source
 member :: Ord a => a -> Heap a -> Bool Source
 count :: Ord a => a -> Heap a -> Int Source
 strict :: Heap a -> Heap a Source
 structuralInvariant :: Ord a => Heap a -> Bool Source
Coll operations
 toSeq :: (Ord a, Sequence s) => Heap a -> s a Source
 lookup :: Ord a => a -> Heap a -> a Source
 lookupM :: (Ord a, Monad m) => a -> Heap a -> m a Source
 lookupAll :: (Ord a, Sequence s) => a -> Heap a -> s a Source
 lookupWithDefault :: Ord a => a -> a -> Heap a -> a Source
 fold :: Ord a => (a -> b -> b) -> b -> Heap a -> b Source
 fold' :: Ord a => (a -> b -> b) -> b -> Heap a -> b Source
 fold1 :: Ord a => (a -> a -> a) -> Heap a -> a Source
 fold1' :: Ord a => (a -> a -> a) -> Heap a -> a Source
 filter :: Ord a => (a -> Bool) -> Heap a -> Heap a Source
 partition :: Ord a => (a -> Bool) -> Heap a -> (Heap a, Heap a) Source
 strictWith :: (a -> b) -> Heap a -> Heap a Source
OrdCollX operations
 deleteMin :: Ord a => Heap a -> Heap a Source
 deleteMax :: Ord a => Heap a -> Heap a Source
 unsafeInsertMin :: Ord a => a -> Heap a -> Heap a Source
 unsafeInsertMax :: Ord a => a -> Heap a -> Heap a Source
 unsafeFromOrdSeq :: (Ord a, Sequence s) => s a -> Heap a Source
 unsafeAppend :: Ord a => Heap a -> Heap a -> Heap a Source
 filterLT :: Ord a => a -> Heap a -> Heap a Source
 filterLE :: Ord a => a -> Heap a -> Heap a Source
 filterGT :: Ord a => a -> Heap a -> Heap a Source
 filterGE :: Ord a => a -> Heap a -> Heap a Source
 partitionLT_GE :: Ord a => a -> Heap a -> (Heap a, Heap a) Source
 partitionLE_GT :: Ord a => a -> Heap a -> (Heap a, Heap a) Source
 partitionLT_GT :: Ord a => a -> Heap a -> (Heap a, Heap a) Source
OrdColl operations
 minView :: (Ord a, Monad m) => Heap a -> m (a, Heap a) Source
 minElem :: Ord a => Heap a -> a Source
 maxView :: (Ord a, Monad m) => Heap a -> m (a, Heap a) Source
 maxElem :: Ord a => Heap a -> a Source
 foldr :: Ord a => (a -> b -> b) -> b -> Heap a -> b Source
 foldr' :: Ord a => (a -> b -> b) -> b -> Heap a -> b Source
 foldl :: Ord a => (b -> a -> b) -> b -> Heap a -> b Source
 foldl' :: Ord a => (b -> a -> b) -> b -> Heap a -> b Source
 foldr1 :: Ord a => (a -> a -> a) -> Heap a -> a Source
 foldr1' :: Ord a => (a -> a -> a) -> Heap a -> a Source
 foldl1 :: Ord a => (a -> a -> a) -> Heap a -> a Source
 foldl1' :: Ord a => (a -> a -> a) -> Heap a -> a Source
 toOrdSeq :: (Ord a, Sequence s) => Heap a -> s a Source
 unsafeMapMonotonic :: (a -> b) -> Heap a -> Heap b Source
Documentation
 moduleName :: String Source