EdisonCore-1.2.1.2: A library of efficent, purely-functional data structures (Core Implementations)Source codeContentsIndex
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
moduleName :: String
Type of splay heaps
data Heap a Source
show/hide 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 aSource
singleton :: a -> Heap aSource
fromSeq :: (Ord a, Sequence s) => s a -> Heap aSource
insert :: Ord a => a -> Heap a -> Heap aSource
insertSeq :: (Ord a, Sequence s) => s a -> Heap a -> Heap aSource
union :: Ord a => Heap a -> Heap a -> Heap aSource
unionSeq :: (Ord a, Sequence s) => s (Heap a) -> Heap aSource
delete :: Ord a => a -> Heap a -> Heap aSource
deleteAll :: Ord a => a -> Heap a -> Heap aSource
deleteSeq :: (Ord a, Sequence s) => s a -> Heap a -> Heap aSource
null :: Heap a -> BoolSource
size :: Heap a -> IntSource
member :: Ord a => a -> Heap a -> BoolSource
count :: Ord a => a -> Heap a -> IntSource
strict :: Heap a -> Heap aSource
structuralInvariant :: Ord a => Heap a -> BoolSource
Coll operations
toSeq :: (Ord a, Sequence s) => Heap a -> s aSource
lookup :: Ord a => a -> Heap a -> aSource
lookupM :: (Ord a, Monad m) => a -> Heap a -> m aSource
lookupAll :: (Ord a, Sequence s) => a -> Heap a -> s aSource
lookupWithDefault :: Ord a => a -> a -> Heap a -> aSource
fold :: Ord a => (a -> b -> b) -> b -> Heap a -> bSource
fold' :: Ord a => (a -> b -> b) -> b -> Heap a -> bSource
fold1 :: Ord a => (a -> a -> a) -> Heap a -> aSource
fold1' :: Ord a => (a -> a -> a) -> Heap a -> aSource
filter :: Ord a => (a -> Bool) -> Heap a -> Heap aSource
partition :: Ord a => (a -> Bool) -> Heap a -> (Heap a, Heap a)Source
strictWith :: (a -> b) -> Heap a -> Heap aSource
OrdCollX operations
deleteMin :: Ord a => Heap a -> Heap aSource
deleteMax :: Ord a => Heap a -> Heap aSource
unsafeInsertMin :: Ord a => a -> Heap a -> Heap aSource
unsafeInsertMax :: Ord a => a -> Heap a -> Heap aSource
unsafeFromOrdSeq :: (Ord a, Sequence s) => s a -> Heap aSource
unsafeAppend :: Ord a => Heap a -> Heap a -> Heap aSource
filterLT :: Ord a => a -> Heap a -> Heap aSource
filterLE :: Ord a => a -> Heap a -> Heap aSource
filterGT :: Ord a => a -> Heap a -> Heap aSource
filterGE :: Ord a => a -> Heap a -> Heap aSource
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 -> aSource
maxView :: (Ord a, Monad m) => Heap a -> m (a, Heap a)Source
maxElem :: Ord a => Heap a -> aSource
foldr :: Ord a => (a -> b -> b) -> b -> Heap a -> bSource
foldr' :: Ord a => (a -> b -> b) -> b -> Heap a -> bSource
foldl :: Ord a => (b -> a -> b) -> b -> Heap a -> bSource
foldl' :: Ord a => (b -> a -> b) -> b -> Heap a -> bSource
foldr1 :: Ord a => (a -> a -> a) -> Heap a -> aSource
foldr1' :: Ord a => (a -> a -> a) -> Heap a -> aSource
foldl1 :: Ord a => (a -> a -> a) -> Heap a -> aSource
foldl1' :: Ord a => (a -> a -> a) -> Heap a -> aSource
toOrdSeq :: (Ord a, Sequence s) => Heap a -> s aSource
unsafeMapMonotonic :: (a -> b) -> Heap a -> Heap bSource
Documentation
moduleName :: StringSource
Produced by Haddock version 2.3.0